Binary Search

發表於 | 分類於 ，

觀念

O(logN)，想法簡單，細節是魔鬼。溢位、mid是加一減一、while()用<= 還是<。
注意搜尋區間和while終止條件
搜尋左右邊界，只要修改nums[mid] ==target 條件處

題目

  • 34 Find First and Last Position of Element in Sorted Array (Medium)
  • 35 Search Insert Position (Easy)
  • 209 Minimum Size Subarray Sum
  • *354 Russian Doll Envelopes (Hard)
  • 392 Is Subsequence (Easy)
  • 658 Find K Closest Elements
  • 704 Binary Search (Easy)
  • 793 Preimage Size of Factorial Zeroes Function (Hard)
  • 875 Koko Eating Bananas (Medium)
  • 2594 Minimum Time to Repair Cars (Medium)
  • 1011 Capacity To Ship Packages Within D Days (Medium)
  • 1870 Minimum Speed to Arrive on Time
  • 1898 Maximum Number of Removable Characters
  • 2226 Maximum Candies Allocated to K Children
  • 410 Split Array Largest Sum (Hard)

補充

  • *4 Median of Two Sorted Arrays
  • 33 Search in Rotated Sorted Array
  • 81 Search in Rotated Sorted Array II
  • 69 Sqrt(x)
  • 153 Find Minimum in Rotated Sorted Array
  • 154 Find Minimum in Rotated Sorted Array II
  • 167 Two Sum II - Input Array Is Sorted
  • 274 H-Index
  • 275 H-Index II
  • 278 First Bad Version
  • *300 Longest Increasing Subsequence
  • *315 Count of Smaller Numbers After Self (Hard)
  • 334 Increasing Triplet Subsequence
  • 374 Guess Number Higher or Lower
  • 475 Heaters
  • 611 Valid Triangle Number
  • 633 Sum of Square Numbers
  • 1283 Find the Smallest Divisor Given a Threshold
  • 1894 Find the Student that Will Replace the Chalk
  • 2187 Minimum Time to Complete Trips (Medium)

Binary Search 框架與變形

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

int binarySearch(int[] nums, int target) {
    int left = 0, right = ...;

    while(...) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            ...
        } else if (nums[mid] < target) {
            left = ...
        } else if (nums[mid] > target) {
            right = ...
        }
    }
    return ...;
}

int binarySearch(int[] nums, int target) {
    int left = 0; 
    int right = nums.length - 1; // 注意

    while(left <= right) {
        int mid = left + (right - left) / 2;
        if(nums[mid] == target) // 停止搜索
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1; // 注意
        else if (nums[mid] > target)
            right = mid - 1; // 注意
    }
    return -1;
}

  • 盡量不要出現else，所有情況都寫清楚。
  • 終止條件left == right
    QA
  1. 為什麼 while 迴圈條件是<= 而不是 <
    因為right ＝ nums.leagth-1 ，而不是nums.length，區別相當於：前者是[left, right]，後者是[left, right)，因為索引大小為nums.length是越界的。

也可以這樣寫

1
2
3
4
5
//...
while(left < right) {
    // ...
}
return nums[left] == target ? left : -1;

左側邊界的二元搜尋(較普及的寫法)
[1,2,2,2,3] 尋找所有２的位置

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
// option 1 
int left_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0;
    int right = nums.length; // 注意

    while (left < right) { // 注意
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid; // 注意
        }
    }
    return left;
}

// option 2 
int left_bound(int[] nums, int target) {
    // 搜索区间为 [left, right]
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        // if else ...
    
        if (nums[mid] < target) {
            // 搜索区间变为 [mid+1, right]
            left = mid + 1;
        } else if (nums[mid] > target) {
            // 搜索区间变为 [left, mid-1]
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 收缩右侧边界
            right = mid - 1;
        }
    }
    if (left >= nums.length || nums[left] != target) // 检查越界
        return -1;
    return left;
}
  • 因為 while(left< right) ，終止條件left == right，搜尋區間 [left, right)
  • 因為 搜尋區間 [left, right) ，會 分成兩區間 [left, mid) 和 [mid+1, right)
  • 返回left 和 right 都一樣意思，因為終止條件是 left== right

右側邊界的二元搜尋

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

int right_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0, right = nums.length;

    while (left < right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            left = mid + 1; // 注意
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    
    if(l==0) return -1;  // 注意
    return nums[l-1]==target?l-1:-1;  // 注意
}
  • 因為終止條件是 left== right ， 所以return left-1 和 return right-1 都一樣。
  • 因為left = mid + 1; while迴圈結束時，nums[left] 一定不等於target，而nums[left-1]可能是target

統一左右兩側邊界的二元搜尋

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int right_bound(int[] nums, int target) {
    int l = 0, r = nums.size()-1;
        while(l<=r){
            int mid = l + (r-l)/2;
            if(nums[mid] == target){
                // return mid;
                r = mid-1; // left bound
                // l = mid+1 ; // right bound
                    
            }
            else if(nums[mid]<target) l = mid+1;
            else r = mid -1 ;
        }
        // left bound
        if(l>= nums.size() || nums[l]!=target) return -1;
        return l;
        //right bound
        // if(r<0 || nums[r]!=target) return -1;
        // return r;
}