Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Problem Challenge 2: Search in Rotated Array

Problem Statement

Given an array of numbers which is sorted in ascending order and also rotated by some arbitrary number, find if a given ‘key’ is present in it.

Write a function to return the index of the ‘key’ in the rotated array. If the ‘key’ is not present, return -1. You can assume that the given array does not have any duplicates.

Note: You need to solve the problem in O(logn) time complexity.

Example 1:

Input: [10, 15, 1, 3, 8], key = 15
Output: 1
Explanation: '15' is present in the array at index '1'.

Example 2:

.....

.....

.....

Like the course? Get enrolled and start learning!
O

Or

· 4 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
M

Mike Xu

· 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
Santha Kumar Ramaiyan

Santha Kumar Ramaiyan

· 2 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).

Mohammed Dh Abbas

Mohammed Dh Abbas

· 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