*Binary Search - ALawliet/algorithms GitHub Wiki
- https://leetcode.com/discuss/general-discussion/786126/Python-Powerful-Ultimate-Binary-Search-Template.-Solved-many-problems
- https://medium.com/swlh/binary-search-cheat-sheet-for-coding-interviews-9c5425af357e
- https://www.geeksforgeeks.org/variants-of-binary-search/
def binarysearch(A, n, T):
l = 0
r = n - 1
while l <= r:
m = (l + r) // 2
if A[m] == T:
return m
elif A[m] < T:
l = m + 1
elif A[m] > T:
r = m - 1
return -1
- use
r = n
withwhile l < r
andA[m] < T
to setl
(recommended, on wikipedia) - use
r = n - 1
withwhile l <= r
andA[m] >= T
to setr
(whichever way the arrow points you want to set that side's variable < = set l, > = set r)
binary search first/leftmost (most common template)
def binarysearch_first_leftmost(A, T):
l = 0
r = n
while l < r:
m = (l + r) // 2
if not cond(): # A[m] < T
l = m + 1 # move right
else:
r = m # move left
return l
l = bisect.bisect_left(A, T)
you can also do it with r = n - 1
and while l <= r
and r = m - 1
def firstBadVersion(self, n):
l = 0
r = n - 1
while l <= r:
m = (l + r) // 2
if isBadVersion(m) == False:
l = m + 1
else:
r = m - 1
return l
binary search last/rightmost
def binarysearch_last_rightmost(A, T):
l = 0
r = n
while l < r:
m = (l + r) // 2
if not notcond(): # A[m] > T
r = m # move left
else:
l = m + 1 # move right
return r - 1 # easiest to forget
r = bisect.bisect_right(A, T)
def firstBadVersion(self, n):
l, r = 0, n - 1
while l <= r:
m = (l + r) // 2
if isBadVersion(m) == True:
r = m - 1
else:
l = m + 1
return r
smallest greater than
class Solution:
def nextGreatestLetter(self, A: List[str], T: str) -> str:
n = len(A)
L = 0
R = n - 1
ans = A[0]
while L <= R:
m = (L + R) // 2
if A[m] > T:
ans = A[m]
R = m - 1
else:
L = m + 1
return ans
weird r = n - 1
with while l < r
cases
v
# usually it's like FFFTTT and you want to find the first T met which is after the last F where it fails L = F + 1 or the first where it passes R = m
def binarysearch(A):
l, r = 0, cols - 1 # n - 1 WHY!?
while l < r:
m = (l + r ) // 2
if binaryMatrix.get(row, m) == 0: # typical first/leftmost binary search where cond not met
l = m + 1
else:
r = m
return l
class Solution:
def findPeakElement(self, A: List[int]) -> int:
n = len(A)
l, r = 0, n - 1
while l < r:
m = (l + r) // 2
if A[m] < A[m+1]:
l = m + 1
else:
r = m
return r