二分查找(经典)

思路分析

  1. 首先确定该数组中间元素的下标mid = (l+r)/2
  2. 然后让要查找的目标值与中间值比对
    • 如果targetVal > arr[mid]，则说明要查找的值在右边，需要递归向右查询
    • 如果targetVal < arr[mid]，则说明要查找的值在左边，需要递归向左查询
    • 如果targetVal == arr[mid]，已找到目标值
  3. 什么时候需要退出递归？
    • 找到就结束递归
    • 遍历完整个数组都没找到，即left>right时

图解演示找不到的情况:

image-20241101205538157 image-20241101205646047 image-20241101205747596

代码实现

递归实现1

查找返回一个符合条件的值

BinarySearch

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
package com.yukinoshita.algorithm.search;

public class BinarySearch {
    public static void main(String[] args) {
        //使用二分的前提：数组有序(ASC or DESC)
        int[] arr = {1, 4, 8, 19, 53, 84, 190, 201};
        int target = 201;
        int targetIndex = binarySearch(arr, 0, arr.length - 1, target);
        if (targetIndex != -1) {
            System.out.printf("目标值%d的下标为：%d\n", target, targetIndex);
        } else {
            System.out.println("找不到该值");
        }

    }

    public static int binarySearch(int[] arr, int left, int right, int target) {
        int targetIndex = -1;
        if (left > right) {
            return targetIndex;
        }

        int mid = left + (right - left) / 2;
        if (target > arr[mid]) {
            targetIndex = binarySearch(arr, mid + 1, right, target);
        } else if(target < arr[mid]) {
            targetIndex = binarySearch(arr, left, mid - 1, target);
        }else{
            targetIndex = mid;
        }
        return targetIndex;
    }
}

递归实现2

上述算法实现仅能返回一个符合条件的目标值的下标，下面进行修改

修改思路为：

当二分查找内部进入else语句时，说明已经找了了某个值，后续就是return语句。

所以我们可以在else中：先将mid加入到list中，再向左、右邻近元素查询，若还有目标值就加入，方法返回类型也改为List。

下面是核心部分修改：

方法binarySearch2()

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
public static ArrayList binarySearch2(int[] arr, int left, int right, int target) {
        if (left > right) {
            return new ArrayList<Integer>();
        }

        int mid = left + (right - left) / 2;
        if (target > arr[mid]) {
            return binarySearch2(arr, mid + 1, right, target);
        } else if (target < arr[mid]) {
            return binarySearch2(arr, left, mid - 1, target);
        } else {
            ArrayList<Integer> resIndexList = new ArrayList<>();
            int temp = mid - 1;
            while (true) {//说明左边已经没有target了
                if (temp < 0 || arr[temp] != target) {
                    break;
                }
                resIndexList.add(temp);
                temp--;
            }

            temp = mid + 1;
            while (true) {
                if (temp >= arr.length || arr[temp] != target) {
                    break;
                }
                resIndexList.add(temp);
                temp++;
            }
            resIndexList.add(mid);
            return resIndexList;
        }
    }

非递归实现

BinarySearch

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
package com.yukinoshita.algorithm.binarySearchNoRecur;

public class BinarySearchNoRecur {
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 12, 16, 20};
        System.out.println("查找下标为："+binarySearch(arr,11));
    }

    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == target) return mid;
            else if (arr[mid] > target) right = mid - 1;
            else left = mid + 1;
        }
        return -1;
    }
}