- 二分查找算法介绍
- 二分查找算法的思路分析
- 二分查找算法(非递归)代码实现
- 二分查找算法(递归)代码实现
- 查找数组中只有一个结果的
- 查找数组中有多个结果的
1. 二分查找算法(非递归)介绍
- 二分查找法只使用从有序的数列中进行查找(比如数字或字母等)，将数列排序后再进行查找
- 二分查找的运行时间为
O(log2 n)，即查找到的目标位置最多只需要log2 n步 。
2.二分查找算法的思路分析
- 思路分析
首先确定数组的中间的下标
mid=(left+right)/2然后让需要查找的数 findVal 和 arr[mid] 比较
2.1
findVal > arr[mid],说明查找的数在 mid 的右边，需要递归向右查找 或 右移查找2.2
findVal < arr[mid], 说明查找的数在 mid 的左边，需要递归向左查找 或 左移查找2.3
findVal == arr[mid]，说明找到，就返回
- 什么时候结束递归或循环
- 找到就结束
- 递归完整个数组，仍没有找到，当
left > right就退出
3. 二分查找算法(非递归)代码实现
public class BinarySearchNoRecur {
public static void main(String[] args) {
//测试
int[] arr = {1,3,8,10,11,67,100};
int index = binarySearch(arr,9);
System.out.println("index=" + index); //
}
/**
* 二分查找的非递归实现
* @param arr 待查找的数组，arr是升序排序
* @param target 需要查找的数
* @return 返回对应下标，-1表示没有找到
*/
public static int binarySearch(int[] arr,int target){
int left = 0;
int right = arr.length - 1;
while(left <= right){ //说明可以继续查找
int mid = (left + right) / 2;
if(arr[mid] == target){
return mid;
}else if(arr[mid] > target){
right = mid - 1; //需要左移查找
}else if(arr[mid] < target){
left = mid + 1; //需要向右边查找
}
}
return -1;
}
}
4.二分查找算法(递归)代码实现
4.1查找数组中只有一个结果的
/**
* 二分查找法(只能找到一个结果)
* @param arr 数组
* @param left 左边的索引
* @param right 右边的索引
* @param findVal 要查找的值
* @return 如果找到就返回下标，如果没有找到，就返回-1
*/
public static int binarySearch(int[] arr,int left,int right,int findVal){
if(left > right){
return -1;
}
int mid = (left + right) / 2;
int midVal = arr[mid];
if(findVal > midVal){ //向右递归
return binarySearch(arr,mid+1,right,findVal);
}else if(findVal < midVal){ //向左递归
return binarySearch(arr,left,mid - 1,findVal);
}else { //找到了
return mid;
}
}
4.2 查找数组中有多个结果的
//将有序数组中的所有数值都查找到
//思路：
//1. 在找到 mid 索引值，不要马上返回
//2. 向 mid 索引的左边扫描，将所有满足1000 的元素的下标，加入到集合ArrayList
//3. 向 mid 索引的右边扫描， 将所有满足1000 的元素的下标，加入到集合 ArrayList
//4. 返回ArrayList
public static List<Integer> binarySearch2(int[] arr, int left, int right, int findVal){
if(left > right){
return new ArrayList<>();
}
int mid = (left + right) / 2;
int midVal = arr[mid];
if(findVal > midVal){ //向右递归
return binarySearch2(arr,mid+1,right,findVal);
}else if(findVal < midVal){ //向左递归
return binarySearch2(arr,left,mid - 1,findVal);
}else { //找到了
List<Integer> resIndexList = new ArrayList<>();
//向 mid 索引的左边扫描，将所有满足1000 的元素的下标，加入到集合ArrayList
int temp = mid - 1;
while (true){
if(temp < 0 || arr[temp] != findVal){
break;
}
//否则，就把temp放入 resIndexList
resIndexList.add(temp);
temp -= 1; //将temp 左移
}
resIndexList.add(mid);
//向 mid 索引的右边扫描， 将所有满足1000 的元素的下标，加入到集合 ArrayList
temp = mid + 1;
while (true){
if(temp > arr.length-1 || arr[temp] != findVal){
break;
}
//否则，就把temp放入 resIndexList
resIndexList.add(temp);
temp += 1; //将temp 左移
}
return resIndexList;
}
