二分查找

发表于 分类于 Waline：

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

二分查找的思想：

  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;
        }
    }