Binary Search Examples

Truthy Left

def binarySearch(self, myList, target)
#  looking for value in myList ,valid range just outside the myList bounds
  a, b = -1, len(myList)
  while b - a > 1:  # while there more than one element
    mid = (a + b) // 2
    if myList[mid] < target: # what condition needs to be true so that
                             # we can move a to the right
      a = mid
    else: 
      b = mid

  if b != len(myList) and myList[b] == target: # check that b has moved, 
                                              # if it has not then the 
                                              # target is not in the myList
    return b
  return -1

target = 6
myList = [0 1 2 3 4 5 6 7 8]
binarySearch(myList, target)

Truthy Right

def binarySearch(self, myList, target)
#  looking for value in myList ,valid range just outside the myList bounds
  a, b = -1, len(myList)
  while b - a > 1:  # while there more than one element
    mid = (a + b) // 2
    if myList[mid] > target: # what condition needs to be true so that
                             # we can move a to the right
      a = mid
    else: 
      b = mid

  if b != len(myList) and myList[b] == target: # check that b has moved, 
                                              # if it has not then the 
                                              # target is not in the array
    return b
  return -1

target = 6
myList = [8 7 6 5 4 3 2 1 0]
binarySearch(myList, target)

Rotated Array - Find Index

class Solution:
    def findFlip(self, myList):
      a, b = -1, len(myList)

      endVal = myList[b-1]
      while b - a > 1:
        mid = (a + b) // 2
        if myList[mid] > endVal: 
          a = mid

        else:
          b = mid

      if b != len(myList):
        return b
      return -1

    def bs(self, myList, target):
      a, b = -1, len(myList)
      while b - a > 1:
        mid = (a + b) // 2
        if myList[mid] < target:
          a = mid
        else: 
          b = mid
      if b != len(myList) and myList[b] == target:
        return b
      return -1

    def search(self, nums: List[int], target: int) -> int:
      if len(nums) == 1:
        if target == nums[0]:
          return 0
        else:
          return -1
      flipIdx = self.findFlip(nums)
      offset = -1 
      ans = 0
      if target < nums[0] and target <= nums[len(nums) - 1] or flipIdx == 0:
        # Search right half
        rightList = nums[flipIdx:]
        offset = self.bs(rightList, target)
        if offset != -1:
          ans = offset + flipIdx
      else:
        leftList = nums[:flipIdx]
        offset = self.bs(leftList, target)
        if offset != -1:
          ans = offset 

      if offset != -1:
        return ans
      return -1

> Input: nums = [4,5,6,7,0,1,2], target = 0
> Output: 4