*Binary Search - ALawliet/algorithms GitHub Wiki

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 with while l < r and A[m] < T to set l (recommended, on wikipedia)
use r = n - 1 with while l <= r and A[m] >= T to set r

(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

*Binary Search - ALawliet/algorithms GitHub Wiki

⚠️ **GitHub.com Fallback** ⚠️

⚠️ GitHub.com Fallback ⚠️