Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Problem Challenge 2: Search in Rotated Array (medium)

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 2 years ago



class Solution:
  def search(self, arr, key):
    # standard binary search 
    def binary_search(b, e):
      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

    '''
      original array 
      1 2 3 4 5 6 7 8 9 10 11 12

      case: 1 b < m > e
      4 5 6 7 8 9 10 11 12 1 2 3
      ^           ^            ^
      b           m            e
      if key in the sorted range 
          do binary search 
      else:
          discard the sorted side
          
      case 2:  b > m < e
      10 11 12 1 2 3 4 5 6 7 8 9
      ^          ^             ^
      b          m             e
      if key in the sorted range 
          do binary search
Show 1 reply
A

Anonymous

· 3 years ago

The problem statement should say the solution should be in the order of log(n). Otherwise, it is a very trivial problem since we can just find the index of the key in the input array and return which just takes o(n).

A

Anonymous

· 4 years ago

In the similar problem, why is it that "the best we can do is to skip one number from both ends"?

Thanks

Show 2 replies
A

Anonymous

· 5 years ago

״However, if there are duplicates, it is not always possible to know which part is sorted. We will look into this case in the ‘Similar Problems’ section.״

But there is no such section.

Show 1 reply

Reading Progress

0%

Vote for new content