Binary Search | LeetCode The Hard Way

Binary search is the searching strategy that reduces the search space by half every iteration until you have found the target.

Please refer the tutorial guide for more details.

int search(vector<int>& nums, int target) {
    // init possible boundary
    int n = nums.size(), l = 0, r = n - 1;
    while (l < r) {
        // get the middle one
        // for even number of elements, take the upper one
        int m = l + (r - l + 1) / 2;
        // exclude m (condition not fulfilled)
        if (target < nums[m]) r = m - 1;
        // include m
        else l = m;
    }
    return nums[l] == target ? l : -1;
}

int search(vector<int>& nums, int target) {
    // init possible boundary
    int n = nums.size(), l = 0, r = n - 1;
    while (l < r) {
        // get the middle one
        // for even number of elements, take the lower one
        int m = l + (r - l) / 2;
        // exclude m (condition not fulfilled)
        if (target > nums[m]) l = m + 1;
        // include m
        else r = m;
    }
    return nums[l] == target ? l : -1;
}