在学习Java的最初阶段,我们应该都写过一个猜数字的小程序,随机生成一个数字,让我们输入来猜,其实里面就用到了二分查找的思想。

binarysearch

二分查找的思想:

  1. 首先确定该数组的中间下表 mid = (left+right)/2;
  2. 然后让需要查找的数findVal和arr[mid]比较;
  3. 若findVal>arr[mid],说明要查找的数在mid的右边,因此需要递归的向右查找;
  4. 若findVal<arr[mid],说明要查找的数在mid的左边,因此需要递归的向左查找;
  5. 若findVal==arr[mid],说明要查找的数找到,就返回。

结束递归条件:

  1. 找到要查找的数,结束递归
  2. 递归完整个数组,仍然没有找到findVal,也需要结束递归,此时left>right

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* @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;
if (findVal > arr[mid]) {
return binarySearch(arr, mid + 1, right, findVal);
} else if (findVal < arr[mid]) {
return binarySearch(arr, left, mid - 1, findVal);
} else {
return mid;
}
}