Binary search for lowest index of an element

Question

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?

Possible duplicate of [Binary search (bisection) in Python](http://stackoverflow.com/questions/212358/binary-search-bisection-in-python) — Jean-François Fabre, Jan 10 '17 at 16:46
yeah , cool . But I don't want to use bisect_left . Any suggestions ? — S Hristoskov, Jan 10 '17 at 16:55
n=len(arr) is not needed, just add the logic to the if statement below — Fruitspunchsamurai, Jan 10 '17 at 17:02
u mean to change the if statement from if n == 1 to len(arr) == 1 ? — S Hristoskov, Jan 10 '17 at 17:05
Sorry, I should have added that as an edit to the comments, it is more to make the code concise. It doesn't help you understand the part about the m start index — Fruitspunchsamurai, Jan 10 '17 at 17:10
When I run your code, I get IndexError: list index out of range. You don't seem to have anything terminating the code? if you have the list arr = [1,2,3,3,4], you would get m=2 on the first try, but instead of accepting that the value was found, your code would recursively call the function again, this time with a list of arr=[1,2]. — Fruitspunchsamurai, Jan 10 '17 at 17:15
Now, you would no longer find the element as it is no longer in the list segment being searched. Explicitly have a condition for when arr[m] = x, when it is less than x, and finally when it is greater than x. — Fruitspunchsamurai, Jan 10 '17 at 17:17

Fruitspunchsamurai · Answer 1 · 2017-01-10T17:40:09.593

1

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

edited Jan 10 '17 at 17:40

answered Jan 10 '17 at 17:32

Fruitspunchsamurai

408
4
13

Special casing `arr[m-1]` won't work in the general case. `binarySearch([1,2,3,3,3,3,3,4,4], 3)` gives `3` instead of `2`. – wildwilhelm Jan 10 '17 at 17:34
Does that fix it? I have to get back to work and that's the quickest hack I can think of. – Fruitspunchsamurai Jan 10 '17 at 17:40
Nice, that looks better to me. Runtime is no longer logarithmic, tho I'm not sure if that can be guaranteed given OP's question. – wildwilhelm Jan 10 '17 at 17:44
yeah , its a good solution , but as wildwilhelm mentioned ,it isn't in log(n) :/ – S Hristoskov Jan 10 '17 at 17:48
[This](http://stackoverflow.com/questions/10148849/find-lowest-index-of-a-given-value-in-a-presorted-array) seems to be a good solution to your problem. The array is edited to sections that are likely to contain the value. With the array [1,3,3,3,3,3,3,4,4], my solution takes 0.0001163482666015625 while his takes 6.198883056640625e-06. – Fruitspunchsamurai Jan 10 '17 at 18:53
but I'm asked for an implemention of algorithm in log(n) – S Hristoskov Jan 10 '17 at 19:05
The selected answer for the question is log(n). – Fruitspunchsamurai Jan 10 '17 at 19:08
The solution posted by the OP in the thread is similar to mine, where it becomes roughly O(n) at the worst case. The selected answer improves on it by changing the binary search itself. – Fruitspunchsamurai Jan 10 '17 at 19:10

Jai · Answer 2 · 2019-07-19T16:20:01.417

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)

wildwilhelm · Answer 3 · 2017-01-11T18:38:27.443

0

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

edited Jan 11 '17 at 18:38

answered Jan 10 '17 at 17:29

wildwilhelm

4,809
1
19
24

Thank for the suggestion , but my function must find the lowest index. Do you know , how to change the code to find it ? – S Hristoskov Jan 10 '17 at 17:31
what does if not arr mean ? – S Hristoskov Jan 10 '17 at 17:57
Here it means that arr is empty. – wildwilhelm Jan 10 '17 at 18:07
so your last piece of code should be the right implementation ? – S Hristoskov Jan 10 '17 at 18:13
When I try to run it , it gives me this error ValueError: The truth value of an array with more than one element is ambiguous. Use a.any() or a.all() for the if not arr – S Hristoskov Jan 11 '17 at 10:05
Ah, I didn't realise you were using numpy arrays. `len(arr) == 0` should work better. – wildwilhelm Jan 11 '17 at 10:47
Yes, thanks, this works :) have you got any idea how to transform my code in this way without two functions and when the element isnt in the array to return NaN? – S Hristoskov Jan 11 '17 at 11:42
(edit) We can just stuff the one function inside the other. – wildwilhelm Jan 11 '17 at 12:25
So there isnt any way without the defintion of a new function – S Hristoskov Jan 11 '17 at 12:35
[This answer](http://stackoverflow.com/a/10148989/1062499) does it in O(log N) time and using a single function. – wildwilhelm Jan 11 '17 at 12:48
Yes but can it be so edited, that it doesnt require the inner function – S Hristoskov Jan 11 '17 at 13:13
(edit) OK, one recursive function, cribbed from the other answer. – wildwilhelm Jan 11 '17 at 18:39
Thank you for the solution :) – S Hristoskov Jan 12 '17 at 11:54

Binary search for lowest index of an element

3 Answers3