1、二分查找算法

二分查找（Binary Search）也叫作折半查找。二分查找有两个要求，一个是数列有序，另一个是数列使用顺序存储结构（比如数组）。

2、二分查找算法的思路分析

这里以数组[1,8,10,89,1000,1234]为例

  • 首先确定该数组中间元素的下标mid

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
/***
 * 二分查找算法
 * @param arr 要查找的目标数组
 * @param left 本次查找的左边界
 * @param right 本次查找的右边界
 * @param findVal 要查找的值
 * @return findVal在arr中的下标，如果找不到返回-1
 */
public static int binarySearch(int[] arr,int left,int right,int findVal) {
    if(left > right) {
        //如果发现left值大于right值，那么证明此时数组已经递归完毕且数组中没有要寻找的值
        //此时需要返回-1
        return -1;
    }
    int mid = (left + right) / 2;
    int midVal = arr[mid];
    //如果要寻找的值小于当前的midVal
    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);
}

image-20210212170116299

测试找得到的情况

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

image-20210212170225794

5、改进二分查找算法

在一个数组中，如果有多个值与findVal值相同时，要求将这些值的下标都找到

思路分析如下:

  • 在找到mid索引值时，不要马上返回

  • 向mid索引值的左边扫描，将所有等于findVal的元素下标进入到一个集合中

  • 向mid索引值的右边扫描，将所有等于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
/***
 * 二分查找算法
 * @param arr 要查找的目标数组
 * @param left 本次查找的左边界
 * @param right 本次查找的右边界
 * @param findVal 要查找的值
 * @return findVal在arr中的下标，如果找不到返回-1
 */
public static List<Integer> binarySearchAllElements(int[] arr,int left,int right,int findVal) {
    if(left > right) {
        //如果发现left值大于right值，那么证明此时数组已经递归完毕且数组中没有要寻找的值
        //此时需要返回null
        return null;
    }
    int mid = (left + right) / 2;
    int midVal = arr[mid];
    //如果要寻找的值小于当前的midVal
    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) {
            //如果数组下标越界或者左边已经没有与findVal相等的值
            if(temp < 0 || arr[temp] != findVal) {
                //退出
                break;
            }
            resIndexList.add(temp);
            temp -= 1;
        }
        //将mid加入到集合中
        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);
}

image-20210212171648097

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) {
    //如果数组为空直接return -1
    if(arr == null) {
        return -1;
    }
    int left = 0;
    int right = arr.length - 1;
    //在left小于right的情况下进行循环
    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;
        }
    }
    //如果上面没有返回，证明数组中没有findVal，直接返回-1
    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);
}

image-20210212172431234