CODEWITHSUNDEEP
pythonbinary-search
S Hristoskov
S Hristoskov

Reputation: 55

Binary search for lowest index of an element

I want to implement a binary search function which returns the lowest index of the element to be searched. Here is my code:

def binarySearch(arr,x):
    n=len(arr)
    if n==1:
        if arr[0]==x:
            return 0
        else:
            return -1 # not in list
    else:
        m=int(n/2)
        if x <= arr[m]:
            return binarySearch(arr[:m],x)
        else:
            return m+binarySearch(arr[m+1:],x)

However, this doesn't work correctly. Can someone help me?

Upvotes: 1

Views: 1911

Answers (3)

Jai
Jai

Reputation: 3310

Time Complexity: O(log(n))
Space Complexity: O(1)

def index_equals_value_search(arr):

  left, right = 0, len(arr)-1
  lowest = -float('inf')
  while left<=right:   

    mid = (left+right)//2   
    print(mid, left, right, arr[mid])
    if arr[mid] == mid:     
      lowest = min(lowest, mid)
      right = mid-1
    elif arr[mid]<0:
       left = mid+1
    elif arr[mid]<mid:
      left = mid+1
    elif arr[mid]>mid:
      right = mid-1


  if lowest == -float('inf'): 
    return -1
  return lowest


arr = [-6,-5,-4,-1,1,3,5,7]
index_equals_value_search(arr)

Upvotes: 1

wildwilhelm
wildwilhelm

Reputation: 5019

You can find the index of an element which is equal to x by just adding a test for equality into the else part of your function:

def binarySearch(arr,x):
    n=len(arr)
    if n==1:
        if arr[0]==x:
            return 0
        else:
            return -1 # not in list
    else:
        m = int(n/2)
        if x < arr[m]:
            return binarySearch(arr[:m],x)
        elif x == arr[m]:
            return m
        else:
            return m + binarySearch(arr[m+1:],x)

This prevents the problem of recursing past the solution, mentioned by @Fruitpunchsalami

However, this won't get you the lowest index:

>>> binarySearch([1,2,3,3,4,4], 3)
3

Here the right answer would be 2.

A further problem is the handling of elements which are not found, due to the special case of -1. We get:

>>> binarySearch([1,2,3,3,6,6], 4)
2

I would be tempted to suggest a generic solution whereby you find the index of the largest element less than x, and then check the element in the position one up from that one.

Finding the largest element less than x can be done in logarithmic time; checking the element to the right is constant time, so you still get O(log n):

def binarySearch(arr,x):
    '''Returns the lowest index of the element equal to `x` or NaN if not found.'''
    def innerBinarySearch(arr, x):
        '''Find index of largest element strictly less than `x`.'''
        if len(arr) == 0:
            return -1
        m = len(arr) // 2
        if x <= arr[m]:
            return innerBinarySearch(arr[:m], x)
        else:
            return m + 1 + innerBinarySearch(arr[m + 1:], x)

    idx = innerBinarySearch(arr,x) + 1
    if 0 <= idx < len(arr) and arr[idx] == x:
        return idx
    return float('nan')

Do it all in one function:

def binarySearch(arr,x):
    '''Returns the lowest index of the element equal to `x` or NaN if not found.'''
    if len(arr) == 0:
        return float('nan')
    m = len(arr) // 2
    if arr[m] < x:
        return m + 1 + binarySearch(arr[m + 1:], x)
    elif x < arr[m] or (0 < m and arr[m-1] == x):
        return binarySearch(arr[:m], x)
    else:
        return m

Upvotes: 0

Fruitspunchsamurai
Fruitspunchsamurai

Reputation: 404

def binarySearch(arr,x):

    if len(arr) == 0:
        return 0

    else:
        m=int(len(arr)/2)

        if arr[m] == x:
            c = 1

            while arr[m-c] == x:
                c += 1
            return m-c+1

        else:
            if x < arr[m]:
                return binarySearch(arr[:m],x)
            else:
                return binarySearch(arr[m+1:],x)

This fixes your issues while also giving you the lowest index

Upvotes: 1

Related Questions