LeetCode—BinarySearch

#1-Find the position of a number in the array:

// find the position of num in the array;
// return the position(if possible) or -1(if the nums is not exist)
int BinarySearch(vector<int> nums, int target){
    int left = 0, right = nums.size() - 1;
    while(left <= right){
        int mid = left + ((right - left) >> 1);

        if(nums[mid] == target) return mid;

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

#2-Closest but less than target

// closest but less
int GetMidLeft(vector<int> nums, int target){
    int left = 0, right = nums.size() - 1;
    while(left <= right){
        int mid = left + ((right - left) >> 1);
        if(nums[mid] >= target){
            right = mid - 1;
        }else{
            left = mid + 1;
        }
    }
    return right;
}

#3-Closest and bigger that target

// closet and bigger
int GetMidRight(vector<int> nums, int target){
    int left = 0, right = nums.size() - 1;
    while(left <= right){
        int mid = left + ((right - left) >> 1);
        if(nums[mid] >= target){
            right = mid - 1;
        }else{
            left = mid + 1;
        }
    }
    return left;
}

#4-Same to target and leftest

// same to target and leftest
int LeftBound(vector<int> nums, int target){
    if(nums.size() == 0) return -1;
    int left = 0, right = nums.size();
    while(left < right){
        int mid = left + ((right - left) >> 1);
        if(nums[mid] == target){        
            right = mid;
        }else if(nums[mid] < target){
            left = mid + 1;
        }else if(nums[mid] > target){
            right = mid;
        }
    }
    return left;
}

#5-Same to target and rightest

// same to target and rightest
int RightBound(vector<int> nums, int target){
    if(nums.size() == 0) return -1;
    int left = 0, right = nums.size();
    while(left < right){
        int mid = left + ((right - left) >> 1);
        if(nums[mid] == target){
            left = mid + 1;
        }else if(nums[mid] < target){
            left = mid + 1;
        }else if(nums[mid] > target){
            right = mid;
        }
    }
    return left - 1;
}

#6-Binary Search with STL

Using header

• #include <algorithm>

How to use?

• binary_search(arr.begin(), arr.begin()+size, index)
• Function:
• find if an element appears
• Where:
• arr : the finding array;
• size: the array range that you want to find;
• index: the target index;
• Return:
• true/false(bool);
• if index exist in array that return true, otherwise return false;

• lower_bound(arr.begin(), arr.begin()+size(), index)
• Function:
• Find if an element appears;
• The lower_bound() function performs a dichotomous lookup between the first and last in the first-closed and last-open interval, returning the position of the first element greater than or equal to val (return the address). If all elements are less than val, then the position of last will be returned.
• Example:
• example code

int main() {
    vector<int> number = {4,10,11,30,69,70,96,100};
    
    auto pos_1 = lower_bound(number.begin(), number.end(), 9);
    
    // get the position == 1
    cout << pos_1 - number.begin() << endl;
    
    // get the elem == 10
    cout << *pos_1 << endl;

		// Larger than all elements, then it will return the last elem == 8
		auto pos_1 = lower_bound(number.begin(), number.end(), 111);
}

• upper_bound(arr.begin(), arr.begin()+size(), index)
• Function:
• Find the first position greater than a certain element;
• NOT EQUAL!
• Example:

int main() {
    vector<int> number = {4,10,11,30,69,70,96,100};
    
    auto pos_1 = upper_bound(number.begin(), number.end(), 10);
    
    // get the position == 2
    cout << pos_1 - number.begin() << endl;
    
    // get the elem == 11
    cout << *pos_1 << endl;
}