BinarySearch模板

本文最後更新於：2024年1月21日 下午

快速整理一下困擾許久的 binary search template

這個演算法的提出早至 1946 年，雖然原理並不難，但是真的很難 bug free 一次寫好

主要問題來自很容易犯下 Off-by-one error

以至於圖靈獎得主高德納在他 The Art of Computer Programming 3 中如此描述二分搜尋：

Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky…

以下統一使用「左閉右閉」區間

之前本來慣用「左閉右開」，但發現在某些情況下，會需要特別向上取整，或是給出不同返回值，太瑣碎了，乾脆換一套新的，更容易理解。

TL;DR

第一組:

返回值 <= target

返回值 > target

1
2
3
4
5
6
7
8
9
if( nums[mid] <= target ) l = c + 1;
else r = c - 1;

//...
    
//返回值 <= target
return r;
//返回值 > target
return l;

第二組:

返回值 < target

返回值 >= target

1
2
3
4
5
6
7
8
9
if( nums[mid] <= target ) l = c + 1;
else r = c - 1;

//...
    
//返回值 < target
return r;
//返回值 >= target
return l;

這些都不是通靈，是一步一步推論後整理出來，方便記憶的結論！

細節討論

通常有【相等返回】，和四個【一般情況】

  • 相等返回: 若找到 nums[mid] == target 就返回 mid
  • 一般情況
    1. 返回值 >= target
    2. 返回值 > target
    3. 返回值 <= target
    4. 返回值 < target

相等返回

通常是一開始練習二分搜就會寫到的題目

蠻簡單的，檢查到 nums[mid] == target 就返回 mid

情況一: 返回值 >= target

1
2
3
4
5
6
7
8
9
10
11
12
13
// 模版一「一般」情形1: 大於等於
class Solution {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while(l <= r){
            int c = l + (r - l) / 2;
            if(nums[c] < target) l = c + 1; // #1 更新後l左側元素「必」小於target
            else r = c - 1; // #2 更新後r右側「必」大於等於target
        }
        // return (l == nums.length || nums[l] != target) ? -1 : l; // 704題的返回，處理:相等/不等
        return l == nums.length ? -1 : l; // 處理: 相等/剛好大於/不存在
    }
}

情況二: 返回值 > target

1
2
3
4
5
6
7
8
9
10
11
12
// 模版一「一般」情形2: 大於
class Solution {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while(l <= r){
            int c = l + (r - l) / 2;
            if(nums[c] <= target) l = c + 1; // #1 更新後l左側元素「必」小於等於target
            else r = c - 1; // #2 更新後r右側「必」大於target
        }
        return l == nums.length ? -1 : l; // 處理: 剛好大於/不存在
    }
}

情況三: 返回值 <= target

1
2
3
4
5
6
7
8
9
10
11
12
13
// 模版一「一般」情形3: 小於等於
class Solution {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while(l <= r){
            int c = l + (r - l) / 2;
            if(nums[c] <= target) l = c + 1; // #1 更新後l左側「必」小於等於target
            else r = c - 1; // #2 更新後r右側「必」大於target
        }
        // return (r == -1 || nums[r] != target) ? -1 : r; // 704題的返回，處理:相等/不等
        return r; // 處理: 相等/剛好小於/不存在
    }
}

情況四: 返回值 < target

1
2
3
4
5
6
7
8
9
10
11
12
// 模版一「一般」情形4: 小於
class Solution {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while(l <= r){
            int c = l + (r - l) / 2;
            if(nums[c] < target) l = c + 1; // #1 更新後l左側元素「必」小於target
            else r = c - 1; // #2 更新後r右側「必」大於等於target
        }
        return r; // 處理: 相等/剛好小於/不存在
    }
}

Reference: