Authored by Tony Feng
Created on April 1st, 2022
Last Modified on April 1st, 2022
Understanding Binary Search
Intro
- Binary search is often used to efficiently locate an item in a sorted sequence of items.
- It divides the search space in 2 after every comparison.
- Compared to linear search which requires O(N) running time, binary search only takes O(log N) where n is the size of the sequence.
Main Steps of the Algorithm
- Pre-processing
- Sort if collection is unsorted.
- Binary Search
- Using a loop or recursion to divide search space in half after each comparison.
- Post-processing
- Determine viable candidates in the remaining space
When Do We Use Binary Search?
- The array is partially or fully sorted.
- The upper bound of time complexity is O(N) or O(log N).
Templates
There are many variants of binary search, such as [l, r), [l, r], (l, r], etc. We should be careful of loop condition, mid/left/right update and return value.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
# The most common case
class Solution:
def binarySearch(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
if len(nums) == 0:
return -1
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2 # Avoid overflow
if nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid - 1
else:
return mid
# End Condition: left > right
return -1
|
Examples
Leetcode 704 Binary Search
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution:
def search(self, nums: List[int], target: int) -> int:
if not nums or len(nums) == 0:
return -1
l, r = 0, len(nums)-1
while l <= r:
m = l + (r - l) // 2
if nums[m] > target:
r = m - 1
elif nums[m] < target:
l = m + 1
else:
return m
return -1
|
Leetcode 35 Search Insert Position
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
l, r = 0, len(nums)-1
while l < r: # break if l == r
mid = l + (r - l) // 2
if nums[mid] < target:
l = mid + 1
elif nums[mid] > target:
r = mid - 1
else:
return mid
return l if target <= nums[l] else l + 1
|
Leetcode 162 Find Peak Element
1
2
3
4
5
6
7
8
9
10
|
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
l, r = 0, len(nums)-1
while l < r:
m = l + (r - l) // 2
if nums[m] > nums[m+1]:
r = m
else:
l = m + 1
return l
|
Leetcode 74 Search a 2D Matrix
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
nums = []
for nums in matrix:
if nums[-1] >= target: # Find which row the target is in
l, r = 0, len(nums)-1
while l <= r:
mid = l + (r - l) // 2
if nums[mid] < target:
l = mid + 1
elif nums[mid] > target:
r = mid - 1
else:
return True
return False
|
Reference