Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Problem Challenge 1: Search Bitonic Array (medium)

Problem Statement

Given a Bitonic array, find if a given key is present in it. An array is considered bitonic if it is first strictly increasing and then strictly decreasing.

In other words, a bitonic array starts with a sequence of increasing elements, reaches a peak element, and then follows with a sequence of decreasing elements. The peak element is the maximum value in the array.

Write a function to return the index of the key. If the 'key' appears more than once, return the smaller index. If the key is not present, return -1.

Example 1:

Input: [1, 3, 8, 4, 3], key=4

.....

.....

.....

Like the course? Get enrolled and start learning!
Sachin Dev S

Sachin Dev S

· 2 months ago

the test cases is missing this

[1, 3, 8, 12, 10, 7, 3, 1] 10

all the test cases pass if the binary search is only written for ascending part, should also include test cases for descending part

Show 1 reply
Mohammed Dh Abbas

Mohammed Dh Abbas

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

Min Power

· 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