BM17 二分查找-I 思考笔记

数据结构已经基本忘了bushi，这一次我尝试自己写出二分查找的模型

思考笔记：结构化思想，while函数内部：访问数组nums的值，所以要保证取值的下标都要是合法的；while函数外部（跳过或跳出）：查找失败。

要保证进入while函数后，查找失败时能自动跳出while函数：关键在于“充分收缩”，也即在对应情况下，分别进行 b = mid - 1， f = mid+1 的更新赋值，而不只是 = mid，从而保证及时跳出循环。

其他：

关注“向下取整”：mid = （f+b）/2，会自动对f 和b 的中间值向下取整。一开始我是想通过很多if 来堆出正确代码，但是这个特点给代码打补丁的工作添了不少麻烦，最后干脆从头再来

int search(vector<int>& nums, int target) {
        // write code here
        int f = 0;
        int b = nums.size() - 1;
        while (f <= b) {
            int mid = (f + b) / 2;
            int val_mid = nums[mid];
            if (target < val_mid) {
                b = mid-1;
            } else if (target > val_mid) {
                f = mid+1;
            } else {
                return mid;
            }
        }
        return -1;