Skip to content

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