Binary search template

  author ：labuladong
link ：https://leetcode-cn.com/problems/binary-search/solution/er-fen-cha-zhao-xiang-jie-by-labuladong/
source ： Power button （LeetCode）
 

Give a binary search template , Include ： Binary search target value , Left boundary , Right border .

（Java and Python edition ）

It's easy to find the target value directly ,

nums[mid]<target, Compress left left = mid +1

nums[mid]>target, Compress right right = mid -1

nums[mid]==target , return mid

Find the first two parts of the left boundary, similar to , but nums[mid]==target Continue to compress the right boundary , Lock left boundary , Finally, return to the left boundary . Pay attention to handling cross-border situations .

Finding the right boundary is the same as .

int binary_search(int[] nums, int target) {
    int left = 0, right = nums.length - 1; 
    while(left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1; 
        } else if(nums[mid] == target) {
            //  Go straight back to 
            return mid;
        }
    }
    //  Go straight back to 
    return -1;
}

int left_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            //  Don't go back , Lock the left border 
            right = mid - 1;
        }
    }
    //  Finally, check  left  The situation of crossing the border 
    if (left >= nums.length || nums[left] != target)
        return -1;
    return left;
}


int right_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            //  Don't go back , Lock the right border 
            left = mid + 1;
        }
    }
    //  Finally, check  right  The situation of crossing the border 
    if (right < 0 || nums[right] != target)
        return -1;
    return right;
}

class Solution:

    def binary_search(self,nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] < target:
                left = mid + 1
            elif nums[mid] > target:
                right = mid - 1
            elif nums[mid] == target:
                return mid
        return -1

    def left_bound(self,nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] < target:
                left = mid + 1
            elif nums[mid] > target:
                right = mid - 1
            elif nums[mid] == target:
                right = mid -1
        if left >= len(nums) or nums[left] != target:
            return -1
        return left

    def right_bound(self,nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] < target:
                left = mid + 1
            elif nums[mid] > target:
                right = mid - 1
            elif nums[mid] ==target:
                left = mid + 1
        if right < 0 or nums[right] != target:
            return -1
        return right