1

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)
1
  • You can use the bisect module but maybe this is homework? Aug 2, 2013 at 7:06

9 Answers 9

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)
2
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
1

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
1

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")
-1
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
-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))
1
  • 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: it is expected to run in O(log(len(sequence))) time, but lists.sort() makes it o(len(sequence)).
    – greybeard
    Jul 28, 2019 at 1:49
-1
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
-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))
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.
    – greybeard
    Mar 8, 2022 at 21:47
  • Please explain tour code and how it addresses the problem in the question. Mar 11, 2022 at 11:52
-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
2
  • 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, 2022 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.
    – Community Bot
    Jul 31, 2022 at 13:17

Not the answer you're looking for? Browse other questions tagged or ask your own question.