binary search implementation with python

Question

I think I did everything correctly, but the base case return None, instead of False if the value does not exists. I cannot understand why.

def binary_search(lst, value):
    if len(lst) == 1:
        return lst[0] == value

    mid = len(lst)/2
    if lst[mid] < value:
        binary_search(lst[:mid], value)
    elif lst[mid] > value:
        binary_search(lst[mid+1:], value)
    else:
        return True

print binary_search([1,2,4,5], 15)

You can use the bisect module but maybe this is homework? – John La Rooy Aug 02 '13 at 07:06 — John La Rooy, Aug 02 '13 at 07:06

Rohit Jain · Answer 1 · 2013-08-02T07:09:15.790

6

You need to return the result of the recursive method invocation:

def binary_search(lst, value):
    #base case here
    if len(lst) == 1:
        return lst[0] == value

    mid = len(lst)/2
    if lst[mid] < value:
        return binary_search(lst[:mid], value)
    elif lst[mid] > value:
        return binary_search(lst[mid+1:], value)
    else:
        return True

And I think your if and elif condition are reversed. That should be:

if lst[mid] > value:    # Should be `>` instead of `<`
    # If value at `mid` is greater than `value`, 
    # then you should search before `mid`.
    return binary_search(lst[:mid], value)
elif lst[mid] < value:  
    return binary_search(lst[mid+1:], value)

edited Aug 02 '13 at 07:09

answered Aug 02 '13 at 07:03

Rohit Jain

209,639
45
409
525

I just figured that out too. I forgot to return those cases. Thank you! – user1933971 Aug 02 '13 at 07:28
This answer uses slice operation which is `O(k)` in python. A better solution will pass in the original list with start:end indices. See more: http://interactivepython.org/runestone/static/pythonds/SortSearch/TheBinarySearch.html – Roy Jan 24 '18 at 01:23

score 1 · Answer 2 · answered Aug 02 '13 at 07:05

1

Because if return nothing!

if lst[mid] < value:
    binary_search(lst[:mid], value)
    # hidden return None
elif lst[mid] > value:
    binary_search(lst[mid+1:], value)
    # hidden return None
else:
    return True

answered Aug 02 '13 at 07:05

Rustam Safin

812
7
15

score 1 · Answer 3 · answered Aug 02 '13 at 07:06

You need to return from if and elif too.

def binary_search(lst, value):
    #base case here
    if len(lst) == 1:
        return lst[0] == value

    mid = len(lst) / 2
    if lst[mid] < value:
        return binary_search(lst[:mid], value)
    elif lst[mid] > value:
        return binary_search(lst[mid+1:], value)
    else:
        return True

>>> print binary_search([1,2,4,5], 15)
False

score 1 · Answer 4 · answered Aug 25 '21 at 03:04

Binary Search:

def Binary_search(num,desired_value,left,right):
    while left <= right:
        mid = (left + right)//2
        if desired_value == num[mid]:
            return mid
        elif desired_value > num[mid]:
            left = mid + 1
        else:
            right = mid - 1
    return -1
num =[12,15,19,20,22,29,38,41,44,90,106,397,399,635]
desired_value = 41
result = Binary_search(num,desired_value,0,len(num)-1)
if result != -1:
    print("Number found at " + str(result),'th index')
else:
    print("number not found")

score -1 · Answer 5 · answered Jul 15 '15 at 22:42

def rBinarySearch(list,element):
    if len(list) == 1:
        return element == list[0]
    mid = len(list)/2
    if list[mid] > element:
        return rBinarySearch( list[ : mid] , element )
    if list[mid] < element:
        return rBinarySearch( list[mid : ] , element)
    return True

score -1 · Answer 6 · answered Jul 27 '19 at 18:00

-1

def binary_search(lists,x):
    lists.sort()
    mid = (len(lists) - 1)//2
    if len(lists)>=1:
        if x == lists[mid]:
            return True

        elif x < lists[mid]:
            lists = lists[0:mid]
            return binary_search(lists,x)

        else:
            lists = lists[mid+1:]
            return binary_search(lists,x)
    else:
        return False
a = list(map(int,input('enter list :').strip().split()))
x = int(input('enter number for binary search : '))
(binary_search(a,x))

answered Jul 27 '19 at 18:00

vamshi madineni

35
2

1

How does this help understand how an execution of the code from the question returns `None`? The code presented here lacks code comments. `binary_search(sequence, key)` desperately needs a [doc string](https://www.python.org/dev/peps/pep-0008/#documentation-strings): it is *expected* to run in O(log(len(sequence))) time, but `lists.sort()` makes it o(len(sequence)). – greybeard Jul 28 '19 at 01:49

score -1 · Answer 7 · answered Mar 01 '22 at 11:00

def binary_search(arr, elm):
    low, high = 0, len(arr) - 1

    while low <= high:
        mid = (high + low) // 2
        val = arr[mid]
    
        if val == elm:
            return mid
        elif val <= elm:
            low = mid + 1
        else:
            high = mid - 1
        
    return -1


print(binary_search([2, 3, 4, 6, 12, 19, 20, 21], 12)) # 4
print(binary_search([2, 3, 4, 6, 12, 19, 20, 21], 3333)) # -1

score -1 · Answer 8 · answered Mar 08 '22 at 19:34

-1

def Binary_search(li, e, f, l):
    mid = int((f+l)/2)
    if li[mid] == e:
        print("Found",li[mid] )
    elif f == l-1 and li[mid] != e:
        print("Not Found ")
    elif e < li[mid]:
        Binary_search(li, e, f,mid)
    elif e > li[mid]:
        Binary_search(li, e, mid,l)



elements = [1,2,4,6,8,9,20,30,40,50,60,80,90,100,120,130,666]
Binary_search(elements, 120, 0, len(elements))

answered Mar 08 '22 at 19:34

Sar ibra

5
2

1

How does this help understand how an execution of the code from the question returns `None`? Does `Binary_search()` return anything useful? There is the [Style Guide for Python Code](https://www.python.org/dev/peps/pep-0008/#documentation-strings). – greybeard Mar 08 '22 at 21:47
Please explain tour code and how it addresses the problem in the question. – Muhammad Mohsin Khan Mar 11 '22 at 11:52

Manjunath kannur · Answer 9 · 2022-08-01T06:07:18.017

-1

class binar_search:

def __init__(self,arr , element):
    self.arr = arr
    self.element = element

def search(self):
    n = len(self.arr)
    low = 0
    high = n-1
    while(low <= high):
        mid = (low+high)//2
        if self.arr[mid] == self.element:
            return mid
        elif self.arr[mid] < self.element:
            low = mid+1
        else:
            high = mid -1
    return 0

edited Aug 01 '22 at 06:07

answered Jul 29 '22 at 07:48

Manjunath kannur

1
1

1

If the class was in the code block, it looked *Object Disoriented Design*. How does this help understand how an execution of the code from the question returns None? How do you tell *not found* from *found at index 0*? – greybeard Jul 29 '22 at 16:54
As it’s currently written, your answer is unclear. Please [edit] to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers [in the help center](/help/how-to-answer). – Community Jul 31 '22 at 13:17

binary search implementation with python

9 Answers9

Binary Search:

Linked