Leetcode: 704. Binary Search

思路：

将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/二分搜寻演算法