Binary Search

Search For A Single Number

Search with closed interval on both ends [left, right].

1
class Solution:
2
    def binary_search(self, nums: List[int], target: int) -> int:
3
        left, right = 0, len(nums) - 1
4
        while left <= right:
5
            mid = left + (right - left) // 2
6
            if nums[mid] == target:
7
                return mid
8
            elif nums[mid] < target:
9
                left = mid + 1
10
            elif nums[mid] > target:
11
                right = mid - 1
12
        return -1

1
class Solution:
2
    def binary_search(self, nums: List[int], target: int) -> int:
3
        left, right = 0, len(nums) - 1
4
        while left < right:
5
            mid = left + (right - left) // 2
6
            if nums[mid] == target:
7
                return mid
8
            elif nums[mid] < target:
9
                left = mid + 1
10
            elif nums[mid] > target:
11
                right = mid - 1
12
        return left if nums[left] == target else -1

Search For A Range

Search for the left bound of the target:

1
class Solution:
2
    def search_left_bound(self, nums: List[int], target: int) -> int:
3
        left, right = 0, len(nums) - 1
4
        while left <= right:
5
            mid = left + (right - left) // 2
6
            if nums[mid] < target:
7
                left = mid + 1
8
            elif nums[mid] > target:
9
                right = mid - 1
10
            elif nums[mid] == target:
11
                right = mid - 1
12
        if left >= len(nums) or nums[left] != target:
13
            return -1
14
        return left

Search for the right bound of the target:

1
class Solution:
2
    def search_right_bound(self, nums: List[int], target: int) -> int:
3
        left, right = 0, len(nums) - 1
4
        while left <= right:
5
            mid = left + (right - left) // 2
6
            if nums[mid] < target:
7
                left = mid + 1
8
            elif nums[mid] > target:
9
                right = mid - 1
10
            elif nums[mid] == target:
11
                left = mid + 1
12
        if right < 0 or nums[right] != target:
13
            return -1
14
        return right