二分查找

正常实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

public int binarySearch(int[] nums, int key) {
    int l = 0, h = nums.length - 1;
    while (l <= h) {
        int m = l + (h - l) / 2;
        if (nums[m] == key) {
            return m;
        } else if (nums[m] > key) {
            h = m - 1;
        } else {
            l = m + 1;
        }
    }
    return -1;
}

二分查找变种

二分查找可以有很多变种，变种实现要注意边界值的判断。例如在一个有重复元素的数组中查找 key 的最左位置的实现如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

int leftBound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 别返回，锁定左侧边界
            right = mid - 1;
        }
    }
    // 最后要检查 left 越界的情况
    if (left >= nums.length || nums[left] != target)
        return -1;
    return left;
}

寻找右边界

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

int right_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 别返回，锁定右侧边界
            left = mid + 1;
        }
    }
    // 最后要检查 right 越界的情况
    if (right < 0 || nums[right] != target)
        return -1;
    return right;
}

上述在 == 分支上进行一个判断，就可以减少搜索。

1
2
3
4
5

if (mid == 0 || array[mid - 1] != n) {
    return mid;
} else {
    high = mid - 1;
}

四种二分查找变形

运用二分查找

算法框架，使用一个单调函数包装我们要比较的部分：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// 函数 f 是关于自变量 x 的单调递增函数
int f(int x, int[] nums) {
    return nums[x];
}

int leftBound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 别返回，锁定左侧边界
            right = mid - 1;
        }
    }
    // 最后要检查 left 越界的情况
    if (left >= nums.length || nums[left] != target)
        return -1;
    return left;
}

875. 爱吃香蕉的珂珂

 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

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int sum = 0;
        int left = 1, right = (int)Math.pow(10, 9) + 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (isValid(mid, piles) <= h) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    public int isValid(int k, int[] piles) {
        int h = 0;
        for (int i = 0; i < piles.length; i++) {
            h += (int)Math.ceil(piles[i] / (k * 1.0));
            // if (piles[i] % k == 0)
            //     h -= piles[i] / k;
            // else
            //     h -= (piles[i] / k + 1);
        }
        return h;
    }
}

1011. 在 D 天内送达包裹的能力

 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

class Solution {
    public int shipWithinDays(int[] weights, int days) {
        if (weights == null || weights.length == 0)
            return -1;
        int left = weights[0], sum = 0;
        for (int num : weights) {
            left = Math.max(left, num);
            sum += num;
        }
        int right = sum;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (f(mid, weights) <= days) {
                right = mid - 1;
            } else
                left = mid + 1;
        }
        return left;
    }

    public int f(int k, int[] weights) {
        int i = 0, sum = 0, ret = 0;
        while (i < weights.length) {
            sum += weights[i];
            if (sum > k) {
                sum = weights[i];
                ret++;
            }
            i++;
        }
        if (sum != 0)
            ret++;
        return ret;
    }
}