查找算法——二分法

傷城~ 2022-11-13 15:24 239阅读 0赞

# 引言 #

二分法，顾名思义，即一分为二的方法，通常用于判断在某个有序数列中是否存在某个数，由于其优秀的算法思想，时间复杂度一般都是 O(logN) ，通常要 O(N) 的遍历方式更加优秀。

# 一、经典二分法查找 #

最常见的二分查找是有序数列找某数，但并不是所有二分查找都必须有序。

public static boolean exist(int[] sortedArr, int num) {
        if (sortedArr == null || sortedArr.length == 0) 
            return false;
        // 设置边际
        int L = 0, mid = 0, R = sortedArr.length - 1;
        // L .. R
        while (L < R) {
            // 计算mid
            mid = L + ((R - L) >> 1);
            if (sortedArr[mid] == num) {
                return true;
            } else if (sortedArr[mid] > num) {
                // 弃右留左
                R = mid - 1;
            } else {
                // 弃左留右
                L = mid + 1;
            }
        }
        return sortedArr[L] == num;
    }

# 二、其他二分查找题目 #

题目：给定一个有序数组，找 >= 某数最左侧的位置，例如，arr\{1,2,3,3,3,4,4,6,9\},即找到位置 2。

public static int mostLeftIndex(int[] arr, int num) {
        int L = 0, R = arr.length - 1;
        int mostLeftIndex = 0;
        while (L < R) {
            mostLeftIndex = L + ((R - L) >> 1);
            if (arr[mostLeftIndex] >= num) {
                // 弃右留左
                R = mostLeftIndex - 1;
            } else {
                // 弃左留右
                L = mostLeftIndex + 1;
            }
        }
        if (arr[L] == num)
            return L;
        else
            return L + 1;
    }

题目2：局部最小问题，在**无序数组**中，任意相邻两个数不相等，**只要比相邻的数都小，就是局部最小**，找到并返回这样一个局部最小值的位置。

例如，若\[0\]<\[1\]，则\[0\]就是局部最小，\[len-2\]>\[len-1\] 则\[len-1\]就是局部最小， \[i-1\]>\[i\]<\[i+1\]，那么\[i\]就是局部最小。

public static int partialMin(int[] arr) {
        if (arr[0] < arr[1])
            return 0;
        if (arr[arr.length - 2] > arr[arr.length - 1])
            return arr.length - 1;
        int L = 1;
        int R = arr.length - 2;
        int mid = 0;
        while (L < R) {
            mid = L + ((R - L) >> 1);
            if (arr[mid] > arr[mid + 1]) {
                // 弃左留右
                L = mid + 1;
            } else if (arr[mid] > arr[mid - 1]){
                // 弃右留左
                R = mid - 1;
            } else {
                return mid;
            }
        }
        return L;
    }

局部最小问题解析，首先判断 0 和最后一个位置上的数是否为最小，如果都不是，那么在两者中间一定存在一个局部最小。二分，然后看中间位置是否比一侧大，取大于一侧的区间，就形成了最开始的“**两端都不是最小，那么中间一定存在一个最小**” 这样的结构。