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 monotonically increasing and then monotonically 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:

.....

Like the course? Get enrolled and start learning!

M

Min Power

· 4 years ago

Show 1 reply

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

Sachin Dev S

· 8 days ago