0% completed

Order-agnostic Binary Search (easy)

Problem Statement

Given a sorted array of numbers, find if a given number ‘key’ is present in the array. Though we know that the array is sorted, we don’t know if it’s sorted in ascending or descending order. You should assume that the array can have duplicates.

Write a function to return the index of the ‘key’ if it is present in the array, otherwise return -1.

Example 1:

Input: [4, 6, 10], key = 10
Output: 2

Example 2:

Input: [1, 2, 3, 4, 5, 6, 7], key = 5
Output: 4

Example 3:

Input: [10, 6, 4], key = 10
Output: 0

Example 4:

.....

Like the course? Get enrolled and start learning!

P

Pete Stenger

· 4 years ago

S

Suhaib AbdulQuddos

· 2 years ago

class Solution:
  def search(self,arr, key):
    if len(arr) == 0:
      return -1
    if arr[0] == arr[-1]:
      return 0 if arr[0] == key else -1
    inc = arr[-1] > arr[0]
    i = 0
    j = len(arr)-1
    while i < j:
      mid = (i+j)//2
      if arr[mid] == key:
        return mid
      if arr[mid] > key and inc:
        j = mid - 1
      else:
        i = mid +1
    if arr[i] == key:
      return i
    return -1  # element not found

I have this solution, which should work. For example. for the array [1,1,1,1,1] it returns 0, but the solution says that it should return 2. I believe this is a mistake because the problem description does not specify how exactly duplicates should be handled.

nirmal kumar ravi

· 2 years ago

class Solution:
  def search(self,arr, key):
    
    def binary_search(goleft):
      left, right = 0, len(arr) - 1

      while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == key:
          return mid
        elif goleft(key, arr[mid]):
          right = mid - 1
        else:
          left = mid + 1
      
      return -1
    

    is_ascending = arr[0] < arr[-1]

    if is_ascending:
      return binary_search(lambda key,mid: key < mid )
    else:
      return binary_search(lambda key,mid: key > mid )

Siddhartha

· 10 months ago