Bloody binary search

PayPal
pAwtyGs

Go to company page PayPal

pAwtyGs
May 18, 2020 98 Comments

To all my dear fellow Leetcoders. If you see a binary search question in an interview buckle up. There are good chances of bombing the interview if not careful. Binary search is a freaking gold mine for all cornor cases.

I bombed an interview with Amazon a month ago. The question was to find an element in rotated sorted array. All the interview went like this

while time is still there:
write code
cornor case from interviewer
code fails

I called it bloody because there is no way to imagine how low and high behave at cornor cases.

Ever since that interview, whenever I see a binary search question in Leetcode, I close my eyes relax and try to get accepted in one shot (Never happened though)

Edit: Thanks a lot to the community for sharing hell lot of useful techniques in the comments

Amazon Google Eng
98

comments

Want to comment? LOG IN or SIGN UP
  1. TOP
  2. RECENT
  3. OLD
 TOP 98 Comments
  • Binary search is easy af, DP is the real shit
    May 18, 2020 26
  • Google
    fartMchine

    Go to company page Google

    fartMchine
    I had to revisit those particular set of 4-5 questions about 10 times each to completely grasp the logic. It's not very hard but sure is tricky and easy to get wrong. But once you get it you don't mess it up.

    I recommend revisiting these Find element in rotated array, find min in rotated array, find min in rotated array with duplicates, find element in rotated array with duplicates till they are a cakewalk for you.
    May 18, 2020 1
  • The corner cases on the rotated array always messes things up
    May 18, 2020 3
  • Google / Eng
    restinvest

    Go to company page Google Eng

     restinvest
    There's an easy way to do binary search without bloody corner cases. Start with linear search and slap an outer loop on top:
    May 18, 2020 7
  • Radian
    UvFo18

    Radian

    UvFo18
    Just memorize the template....

    Low, high = 0, Len(arr) - 1

    While low <= high:
    Mid = low + (high - low) // 2
    If arr[mid] == target:
    Return mid
    Elif arr[mid] > target:
    High = mid - 1
    Else:
    Low = mid + 1
    Return -1
    May 18, 2020 3
    • Radian
      UvFo18

      Radian

      UvFo18
      So first you make sure that the array is actually rotated. You can do that by comparing the first element with the last element in the array (make sure that it is strictly less than the last, if not, then one binary search will suffice).

      Then, do one binary search to find the rotation point. Then, if the target is greater than the first element in the array, then do a binary search with low = 0, high = rotation point - 1. Else if target < first element in arr, do a binary search with low = rotation, high = len(arr) - 1

      Obv, it’s still log n runtime & o(1) space despite the two while loops.
      May 18, 2020
    • Radian
      UvFo18

      Radian

      UvFo18
      def binarySearch(self, nums, target, low, high):
              while low <= high:
                  mid = (low + high) // 2

                  if nums[mid] == target:
                      return mid
                  elif nums[mid] > target:
                      high = mid - 1
                  else:
                      low = mid + 1
              return -1
              
          
          def search(self, nums: List[int], target: int) -> int:
              if len(nums) == 0:
                  return -1
              
              pivot = -1
              # Find Pivot
              if nums[0] <= nums[-1]:
                  pivot = 0
                  return self.binarySearch(nums, target, 0, len(nums) - 1)
              else:
                  low, high = 1, len(nums) - 1
                  while low <= high:
                      mid = (low + high) // 2
                      if nums[mid - 1] > nums[mid]:
                          pivot = mid
                          break
                      elif nums[mid] < nums[0]:
                          high = mid - 1
                      else:
                          low = mid + 1
              
              if target > nums[-1]:
                  return self.binarySearch(nums, target, 0, pivot - 1)
              else:
                  return self.binarySearch(nums, target, pivot, len(nums))
      May 18, 2020