1、二分查找算法
二分查找(Binary Search)也叫作折半查找。二分查找有两个要求,一个是数列有序,另一个是数列使用顺序存储结构(比如数组)。
2、二分查找算法的思路分析
这里以数组[1,8,10,89,1000,1234]为例
mid = [left+right] / 2
- 让需要查找的数findVal和arr[mid]比较,此时会出现以下几种情况
- findVal>arr[mid],说明要查找的数在mid的右边,因此我们需要递归向右查找
- findVal<arr[mid],说明要查找的数在mid的左边,因此我们需要递归向左查找
- findVal=arr[mid],说明arr[mid]就是我们要寻找的值,直接返回mid
- 结束递归的条件有
- 找到目标值结束递归。
- 递归完整个数组仍然没有找到findVal,也需要结束递归。即当left>right时结束递归。
3、递归二分查找算法的代码实现
递归退出条件1:寻找到目标值,此时返回mid
递归退出条件2:递归完整个数组没有找到目标值,此时left > right,返回-1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
|
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、测试
测试找不到的情况
1 2 3 4 5
| public static void main(String[] args) { int[] arr = {1,8,10,89,1000,1234}; int resultIndex = binarySearch(arr,0, arr.length - 1,10000); System.out.println(resultIndex); }
|

测试找得到的情况
1 2 3 4 5
| public static void main(String[] args) { int[] arr = {1,8,10,89,1000,1234}; int resultIndex = binarySearch(arr,0, arr.length - 1,8); System.out.println("resultIndex:" + resultIndex); }
|

5、改进二分查找算法
在一个数组中,如果有多个值与findVal值相同时,要求将这些值的下标都找到
思路分析如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
|
public static List<Integer> binarySearchAllElements(int[] arr,int left,int right,int findVal) { if(left > right) { return null; } int mid = (left + right) / 2; int midVal = arr[mid]; if(findVal > midVal) { return binarySearchAllElements(arr,mid + 1,right,findVal); } else if(findVal < midVal) { return binarySearchAllElements(arr,left,mid - 1,findVal); } else { List<Integer> resIndexList = new ArrayList<>(); int temp = mid - 1; while(true) { if(temp < 0 || arr[temp] != findVal) { break; } resIndexList.add(temp); temp -= 1; } resIndexList.add(mid); temp = mid + 1; while (true) { if(temp > arr.length - 1 || arr[temp] != findVal) { break; } resIndexList.add(temp); temp += 1; } return resIndexList; } }
|
测试
1 2 3 4 5
| public static void main(String[] args) { int[] arr = {1,5,1000,1000,1000,1234,1999}; List<Integer> result = binarySearchAllElements(arr,0, arr.length - 1,1000); System.out.println("结果下标为:" + result); }
|

6、非递归实现二分查找算法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| public static int binarySearch(int[] arr,int findVal) { if(arr == null) { return -1; } int left = 0; int right = arr.length - 1; while(left <= right) { int mid = (left + right) / 2; if(findVal < arr[mid]) { right = mid - 1; } else if(findVal > arr[mid]) { left = mid + 1; } else { return mid; } } return -1; }
|
测试:
1 2 3 4 5
| public static void main(String[] args) { int[] arr = {1,5,888,1000,1111,1234,1999}; int resIndex = binarySearch(arr,5); System.out.println("resIndex的值为:" + resIndex); }
|
