二分搜尋是一個比循序搜尋還要有效率的常用搜尋方式，主要邏輯為反覆將搜尋範圍減半直到找到目標為止，但是除了最基本的寫法之外還有另外兩種寫法，也有很多小細節是需要注意的。

一點小細節

循環 & 終止條件

  1. left <= right
    當循環條件為 left <= right 時，代表會在 left == right + 1 時結束，此時區間為空，代表可以直接回傳 -1 ，target 不在陣列之中。
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while(left <= right){
            int mid = (left + right) / 2;
            if(nums[mid] == target) return mid;
            else if(nums[mid] > target) right = mid - 1;
            else left = mid + 1;
        }
        return -1;
    }
};
  1. left < right
    當循環條件為 left < right 時，代表會在 left == right 時結束，此時區間內還有一個元素，因此在最後必須檢查該元素是否為 target。
1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while(left < right){
            //相同
        }
        return nums[left] == target? left : -1; //判斷
    }
};

mid 取值

mid 在取值時有兩種寫法，分別為 (left + right) / 2 以及 (left + right + 1) / 2 ，這兩種寫法在陣列長度為奇數時會取到相同的值，但是在偶數時前者會取到中央偏左的值，後者則會取到偏右的值，以 nums.size() == 2 的陣列為例，前者會取到 index 為 0 的位置，後者取到 index 為 1 的位置。

不過這兩種寫法在一般的二分搜尋寫法中最後得到的結果會是相同的，因為二分搜尋的核心是將陣列分段縮小範圍，因此實際上不一定要取正中間的位置，但是等等介紹到的二分搜尋方式中會利用到，以避免死循環。

在處理陣列較長的問題時，因為 left + right 時可能會超過 int 的範圍，為了避免溢位問題，我們也會改變寫法，改為 left + (right - left) / 2 或是 left + (right - left + 1) / 2 ，分別對應到前面提到過的兩種取值。

區間方式

直接法

在區間中找到元素時直接回傳結果，退出循環代表目標不在陣列中。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while(left <= right){
            int mid = (left + right) / 2;
            if(nums[mid] == target) return mid;
            else if(nums[mid] > target) right = mid - 1;
            else left = mid + 1;
        }
        return -1;
    }
};

排除法

不斷排除目標不在的區間。

Type 1

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while(left < right){
            int mid = (left + right + 1) / 2; //注意
            if(nums[mid] > target) right = mid - 1;
            else left = mid;
        }
        return nums[left] == target? left : -1;
    }
};

Type 2

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while(left < right){
            int mid = (left + right) / 2; //注意
            if(nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        return nums[left] == target? left : -1;
    }
};

觀察以上的兩種寫法可以發現，與直接法不同的是，程式不會去主動判斷 nums[mid] == target ，而是不斷的縮小範圍，直到區間只剩下一個數字，目的是使結束時 left == right 方便判斷。

而兩種方法的 mid 取值這時候就有不同之處了，這兩種取值方式可以避免在剩下兩個元素時的死循環，在使用時要特別注意。

比較

直接法因為會在找到目標時直接跳出，因此適合非重複的陣列，否則其在重複陣列找到目標的位置不一定，而使用排除法的兩種方式則分別可以找到右邊界以及左邊界，適合處理較複雜的題目。

方法 直接法 排除法 Type 1 排除法 Type 2
循環條件 left <= right left < right left < right
mid 取值 皆可 (left + right + 1) / 2 (left + right) / 2
left 取值 mid + 1 mid mid + 1
right 取值 mid - 1 mid - 1 mid
應用 非重複陣列 重複陣列右邊界 重複陣列左邊界

練習

LeetCode 34. Find First and Last Position of Element in Sorted Array

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Example 3:
Input: nums = [], target = 0
Output: [-1,-1]

Solution:

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
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> ans(2, -1);
        if(nums.size() == 0) return ans;
        int left = 0, right = nums.size() - 1;
        while(left < right){
            int mid = (left + right) / 2;
            if(nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        if(nums[left] != target) return ans;
        else ans[0] = left;
        
        left = 0;
        right = nums.size() - 1;
        while(left < right){
            int mid = (left + right + 1) / 2;
            if(nums[mid] > target) right = mid - 1;
            else left = mid;
        }
        ans[1] = left;
        return ans;
    }
};

透過排除法的兩種方式找到邊界。

LeetCode 852. Peak Index in a Mountain Array

You are given an integer mountain array arr of length n where the values increase to a peak element and then decrease.

Return the index of the peak element.

Your task is to solve it in O(log(n)) time complexity.

Example 1:
Input: arr = [0,1,0]
Output: 1

Example 2:
Input: arr = [0,2,1,0]
Output: 1

Example 3:
Input: arr = [0,10,5,2]
Output: 1

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int left = 0, right = arr.size() - 1;
        while(left < right){
            int mid = (left + right) / 2;
            if(arr[mid] > arr[mid + 1]) right = mid;
            else left = mid + 1;
        }
        return left;
    }
};

利用 mountain array 的特性， peak element 的左邊有 arr[n] < arr[n + 1] ；右邊則是 arr[n] > arr[n + 1] ，因此可以透過二分搜尋的方式尋找 peak element。