本文主要是介绍数据结构与算法——二分查找,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
基本介绍
![在这里插入图片描述](/upload/202107/29/202107290108331248.png)
代码实现
/**
* 二分查找要求数组有序
* @param arr 数组
* @param left 左索引
* @param right 右索引
* @param value 查找的数据
* @return 包含数据索引的集合
*/
public static ArrayList<Integer> binarySearch(int[] arr, int left, int right, int value) {
//没找到
if (left > right) {
return new ArrayList<Integer>();
}
int mid = (left + right) / 2;
if (value > arr[mid]) { //向右递归
return binarySearch(arr, mid + 1, right, value);
} else if (value < arr[mid]) { //向左递归
return binarySearch(arr, left, mid - 1, value);
} else { //已找到,将数据索引加入集合
ArrayList<Integer> resIndexList = new ArrayList<>();
resIndexList.add(mid);
//向mid左边扫描,将所有与arr[mid]相同的数据放入集合中
int temp = mid-1;
while (temp >= 0 && arr[temp] == value) {
resIndexList.add(temp);
temp--;
}
//向mid右边扫描,将所有与arr[mid]相同的数据放入集合中
temp = mid+1;
while (temp <= arr.length - 1 && arr[temp] == value) {
resIndexList.add(temp);
temp++;
}
return resIndexList;
}
}
这篇关于数据结构与算法——二分查找的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!