【LeetCode-704| 二分查找】

#include <iostream>
#include <vector>


using namespace std;

/* 二分法使用的提示信息：数组元素有序排列、数组中无重复元素 */

/* 区间不变量: 保证在while循环中每次边界的处理都坚持相同的区间定义,[left, right] 或者[left, right)*/
class Solution {
public:
    int bsearch1(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;  // 定义target在左闭右闭的区间里，即：[left, right]
        while(left <= right) {
            int mid = left + (right - left) / 2;   // 防止数据溢出，因此mid的求法不是(left + right) / 2
            if(nums[mid] > target) {
                right = mid - 1;  // [left, mid - 1]
            } else if(nums[mid] < target) {
                left = mid + 1;  // [mid + 1, right]

            } else {
                return mid;
            }
        }
        return -1;
    }

    int bsearch2(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size();  // 定义target在左闭右开的区间里，即：[left, right）

        while(left < right) {
            int mid = left + ((right - left) >> 1);
            if(nums[mid] > target) {
                right = mid;  // [left, mid)
            } else if(nums[mid] < target) {
                left = mid + 1; // [mid + 1, right)
            } else {
                return mid;
            }
        }
        return -1;
    }

};