Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Problem Challenge 1: Search Bitonic Array (medium)

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 2 years ago

class Solution:
  def search(self, arr, key):

    def find_peak_index():
      b, e = 0, len(arr) - 1
      while b <= e:
        m = (b + e) // 2
        if m + 1 < len(arr) and arr[m] < arr[m + 1]:
          b = m + 1
        else:
          e = m - 1 
      return b   

    def seach_item(peak_index, is_left_search):
      if is_left_search:
        b, e = 0, peak_index
      else:
        b, e = peak_index, len(arr) - 1
        
      while b <= e:
        m = (b + e) // 2
        if arr[m] == key:
          return m 
        elif arr[m] < key:
          b = m + 1
        else:
          e = m - 1
      return -1

    peak_index = find_peak_index()
    left_search = seach_item(peak_index, True)
    return left_search if left_search != -1 else seach_item(peak_index, False
A

Anonymous

· 5 years ago

I think there should be a minor tweak to the problem statement. It should say return the first key since the solution offered will only return the first key found but the examples have shown that duplicate values are allowed

Show 1 reply

Reading Progress

0%

Vote for new content