About Binary Search

about Binary Search 二分查找

普通的二分查找

int BinarySearch_nonrecursive(vector<int>& nums, int target) {
    int left = 0, right = (int)nums.size() - 1;
    while (left <= right) {  //不加 = 如果数组长度为1 会错
        int mid = (left + right)/2;
        if (nums[mid] > target) {
            right = mid - 1;
        }
        else if (nums[mid] < target) {
            left = mid + 1;
        }
        else return mid;
    }
    return 0;
}

//递归 
int BinarySearch_recursive(vector<int>& nums, int target, int left, int right) {
    if (left > right) return 0;
    int mid = (left + right) / 2;
    if (nums[mid] > target) return BinarySearch_recursive(nums, target, left, mid - 1);
    else if (nums[mid] < target) return BinarySearch_recursive(nums, target, mid + 1, right);
    else return mid;
    
}

如果你只想要二分查找找到的第一个：

int BinarySearch_First_nonrecursive(vector<int>& nums, int target) { //查找第一个
    int left = 0, right = (int)nums.size() - 1;
    while (left <= right) {
        int mid = (left + right)/2;
        if (nums[mid] < target) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }
    return nums[left] == target ? left : -1;
}

• (l + r + 1) >> 1; 进阶的 (r - l)/2 + l;