思路：

將index不斷除以2以找到對應的值，while條件是在index保持在>=0 && < array size。

思路修正：

因為不斷地根據尋找的邊界限縮，所以index不可能超出前面說的兩個範圍，因此乾脆改成執行for迴圈 log(n)次，並將初始lower bound設為0，upper bound設為array size。

在修正：

還是不對，所以改成用lb, ub去判定。

程式

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int ans = -1;
        int lb = 0, ub = nums.size() - 1;
        while(lb <= ub) {
            //cout << "(" << lb << ", " << ub <<  ", " << index << ")";
            int index = lb + (ub - lb) / 2;
            if ( nums[index] < target ) 
                lb = index + 1;
            else if ( nums[index] > target )
                ub = index - 1;
            else {
                ans = index;
                break;
            }
        }
        return ans;
    }
};

後來

有遇到ERROR: AddressSanitizer: heap-buffer-overflow on address
原因是upper bound 不應該使用arrary size，而是要使用最大index，即array size - 1

參考

https://zh.wikipedia.org/wiki/二分搜尋演算法