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