【数据结构与算法】二分查找算法(C++实现)

两种写法，取决于划分规则。

这两种写法是学的yxc的，至此以后，写二分查找再也不含糊了！

yxc的分享在此：二分查找算法模板

第一种写法：

bool binarySearch(vector<int>& nums, int target) {
    int n = nums.size();
    int left = 0, right = n - 1;
    // while循环不像常见的写法，这里不能加等号，否则死循环
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] >= target) {
            // 所找的target在数组的左半段，缩小right，
            // 注意这里不能减1，因为这里的判断条件有等号
            right = mid;
        } else {
            // 所找的target在数组的右半段
            left = mid + 1;
        }
    }
    // target有可能不在数组中，这里需要检查一下
    if (nums[left] == target) return true;
    return false;
}

第二种写法：

bool binarySearch(vector<int>& nums, int target) {
    int n = nums.size();
    int left = 0, right = n - 1;
    // while循环不像常见的写法，这里不能加等号，否则死循环
    while (left < right) {
        // 注意这里的变化，有加1
        int mid = left + (right - left + 1) / 2;
        if (nums[mid] <= target) {
            // 所找的target在数组的右半段，增大left，
            // 注意这里不能加1，因为这里的判断条件有等号
            left = mid;
        } else {
            // 所找的target在数组的左半段
            right = mid - 1;
        }
    }
    // target有可能不在数组中，这里需要检查一下
    if (nums[left] == target) return true;
    return false;
}