Binary Search
Starred by 25+ users, GitHub Repo: LeetCode Pattern 500 offers:
- 500 solutions for LeetCode problems in Python and Java
- 17 notes on essential concepts related to data structures and algorithms
- 130 patterns for solving LeetCode problems
binary search
intro
# approach 1
# search in a sorted array for specific val
# or search in sth’s range
class Solution:
def binary_search(self, nums, TARGET):
left, right, boundary = 0, len(nums) - 1, - 1
while left <= right:
m = (left + right) // 2
if nums[m] > TARGET:
right = m - 1
elif nums[m] == TARGET:
boundary = m
break
else:
left = m + 1
return boundary
# approach 2
# search in a sorted array for most close val to specific val
# or search in sth’s range
class Solution:
def binary_search(self, nums, LIMIT):
left, right, boundary = LOW_BOUND, UP_BOUND, - 1
def valid(PARAMETERS):
SOME OPS DUE TO LIMIT
return BOOL
while left <= right:
m = (left + right) // 2
if valid(m):
boundary = m
right = m - 1 # or left = m + 1
else:
left = m + 1 # or right = m - 1
return boundary
- an efficient sorted array search algorithm
- can search for specific val
- can search for most close val to specific val
- can make a binary decision to shrink the search range
- time
O(log(n))
, spaceO(1)
- left and right can be a range from
- sorted array’s start and end
- sth’s low_bound and up_bound
- use a boundary (ptr) to record the current best/valid answer, then try to get better one
pattern
search in a sorted array for specific val
- when shrinking, will have 3 logic branch mostly
search in a sorted array for most close val
- when shrinking, will have 2 logic branch mostly
search in sth’s range
- search between sth’s low_bound and up_bound
- num
- length
- capacity
- distance
- total
- sum
- cost
- can be for specific val or for most close val. mostly for most close val
use boundary to record
- depends on different condition, binary search could have different logic branch, and only inside certain branch could record the boundary
- when recording, we should consider the concept of greedy algorithm
- implement
- use - 1 to initiation, to handle not find situation
- inside branch, record most valid answer in cur condition
- or use len(nums) - 1 to initiation, as a potential valid answer
- inside branch, record most valid answer in cur condition
- or doesn’t need it, when it is guaranteed to have a specific answer
- use - 1 to initiation, to handle not find situation
rotated sorted array
- use mid ptr to compare to right ptr (help us to know which side of mid ptr can treat as sorted)
- if mid ptr val larger than right ptr val, means the left side of mid ptr has order
- if mid ptr val less than right ptr val, means the right side of mid ptr has order
- then figure out our target val is
- between left and mid (ascending order)
- not between left and mid (not sure)
- between mid and right (ascending order)
- not between mid and right (not sure)
- notice: above approach is based on the array only contain unique vals
- if contain duplicate vals, when the mid == right (means cannot decide which side could be sorted), we can only wipe out this one element in this round