10

I have a list with numbers from 0-9:

mylist = list(range(10))

I am getting an error with the division command to get mid:

def binary_search(mylist, element, low, high):
    low=0
    high= len(mylist)
    mid=low + (high- mymin)/2
    if mid==len(mylist):
        return False
    elif mylist[mid]==element:
        return mid
    elif high==low:
        return False
    elif mylist[mid]<element:
        return binary_search(mylist, element, mymin, mid-1)
    elif mylist[mid]<element:
        return binary_search(mylist, element, mid+1, mymax)
    else:
        return mid

and if I wanted to return True how would I write that on top of return binary_search(mylist, element, mymin, mid-1)?

Asclepius
  • 57,944
  • 17
  • 167
  • 143
user2898221
  • 157
  • 1
  • 2
  • 6
  • 2
    The first one can't be actual code, because that `list(mid)` is going to raise a `TypeError: 'list' object is not callable`. If you want us to debug your code, you have to show us code that actually demonstrates the problem, not just vaguely similar code. – abarnert Nov 14 '13 at 22:43
  • 4
    As a side note, `list`, `max`, and `min` are all bad names for variables, because they're the names of built-in functions that you may want to use. – abarnert Nov 14 '13 at 22:52

17 Answers17

12

Recursive solution:

def binary_search_recursive(arr, elem, start=0, end=None):
    if end is None:
        end = len(arr) - 1
    if start > end:
        return False

    mid = (start + end) // 2
    if elem == arr[mid]:
        return mid
    if elem < arr[mid]:
        return binary_search_recursive(arr, elem, start, mid-1)
    # elem > arr[mid]
    return binary_search_recursive(arr, elem, mid+1, end)

Iterative solution:

def binary_search_iterative(arr, elem):
    start, end = 0, (len(arr) - 1)
    while start <= end:
        mid = (start + end) // 2
        if elem == arr[mid]:
            return mid
        if elem < arr[mid]:
            end = mid - 1
        else:  # elem > arr[mid]
            start = mid + 1

    return False
Asclepius
  • 57,944
  • 17
  • 167
  • 143
Norah Borus
  • 318
  • 3
  • 8
11

Here's an elegant recursive solution if you're:

1) Trying to return the INDEX of the target in the original list being passed in, before it is halved. Getting the target is the easy part.

2) Only want to have to pass in 2 arguments: (list, target) instead of 4 arguments including the upper/lower (right/left) bounds of each array being passed in recursively.

3) Don't want out of bounds, maximum recursion depth, or target not found errors.

# Base Case: one item (target) in array.
# Recursive Case: cut array by half each recursive call.


def recursive_binary_search(arr, target):
    mid = len(arr) // 2
    if len(arr) == 1:
        return mid if arr[mid] == target else None
    elif arr[mid] == target:
        return mid
    else:
        if arr[mid] < target:
            callback_response = recursive_binary_search((arr[mid:]), target)
            return mid + callback_response if callback_response is not None else None
        else:
            return recursive_binary_search((arr[:mid]), target)
Devin B.
  • 433
  • 4
  • 18
  • 1
    Perfect solution – bn00d Dec 26 '19 at 22:02
  • Doesn't list slicing create a copy of the array? By using indexes you'd be able to save space, if that's a concern. – HanifC Apr 20 '20 at 16:53
  • Not in the way you think. It creates an array of pointers that refer to the memory address of the original array. In other words, it copies the references, which in this case is exactly what we want to return (IE the index of the target) -- that, without its original reference, would be lost when using indexes. Also, I heard using the slice approach in these situations is actually faster. While that might not always be the case, it would be cool to test out. – Devin B. Apr 22 '20 at 00:11
  • 2
    @Dev can you please elaborate on the code part with callback_response? Did I get it right that we need it here to increment the value of the mid value on every iteration while searching right half for the index? – Eugene Anufriev Aug 22 '20 at 18:38
  • 1
    @EugeneAnufriev you are correct sir – so if the target isn't found, slice either side of the array based on the new mid, and pass that as well as the target as arguments to its recursive function. Sorry for the confusion of the "callback_response" variable assignment – I always thought a recursive function was a type of callback function, so then the response for that call would be the callback-response. Please help me find a better name. – Devin B. Aug 26 '20 at 14:22
  • 1
    Really great implementation of the algorithm @Dev. I would just call it "index" instead of "callback_response" since that is exactly what your function returns - the index of target inside arr. – Nevermore Nov 02 '21 at 03:16
  • 1
    Hi @Dev I must say that your solution made me happy. Just like EugeneAnufriev, I was confused with the "callback_response" line until I saw these comments. Your implementation really shows that you understood recursive calls in relation to how recursion calls uses call stack. Thanks man. – KingNOB Jan 18 '22 at 16:54
  • I think the split array should not contain the value on the "mid" index. It means that when searching value 8 in the array [0, 2, 4, 6, 8], the "mid" item is 4 and it should not be contained in the next sliced array which should be equal to [6, 8]. That's how binary search is defined. – Deny Dec 02 '22 at 10:21
  • @Nevermore I agree `callback_response` should be called something else, but I think `offset_idx` might be an even more accurate variable name. – lolololol ol Dec 23 '22 at 01:39
3

please correct me, if the code presents any bugs

def binary_recursive(array, val):
    if val < array[0] or val > array[-1]:
        return False
    mid = len(array) // 2
    left = array[:mid]
    right = array[mid:]
    if val == array[mid]:
        return True
    elif array[mid] > val:
        return binary_recursive(left, val)
    elif array[mid] < val:
        return binary_recursive(right, val)
    else:
        return False
Yossarian42
  • 1,950
  • 17
  • 14
  • RecursionError: maximum recursion depth exceeded while calling a Python object when you pass in a value not in the list. Is there a base case to address this? – Devin B. Aug 15 '19 at 07:32
3

`Please correct me if I am wrong as I am a new programmer but here is my solution:

def binary_search(test_cases, item_to_be_found):
    try:
        if item_to_be_found == test_cases[len(test_cases) // 2]:
            return True
        elif item_to_be_found < test_cases[len(test_cases) // 2]:
            test_cases = test_cases[:len(test_cases) // 2]
        else:
            test_cases = test_cases[len(test_cases) // 2:]
        return binary_search(test_cases, item_to_be_found)
    except RecursionError:
        return False
Mythic
  • 31
  • 5
  • Welcome to SO. Your solution might be correct. However, it would be nice to add some explanation/commented to the code the answer you posted. – Grayrigel Oct 15 '20 at 09:46
  • Ah, I see. I will keep that in mind. Thank you very much! – Mythic Oct 17 '20 at 06:51
2

The first solution looks wrong because it doesn't index the list.

This problem tripped me up too the first time I wrote a solution so be sure to test your algorithm well.

Here's what I ended up with:

def binary_search(value, items, low=0, high=None):
    """
    Binary search function.
    Assumes 'items' is a sorted list.
    The search range is [low, high)
    """

    high = len(items) if high is None else high
    pos = low + (high - low) / len(items)

    if pos == len(items):
        return False
    elif items[pos] == value:
        return pos
    elif high == low:
        return False
    elif items[pos] < value:
        return binary_search(value, items, pos + 1, high)
    else:
        assert items[pos] > value
        return binary_search(value, items, low, pos)

And when I test it, the answers look correct:

In [9]: for val in range(7):
   ...:     print val, binary_search(val, [1, 2, 3, 5])
   ...:
0 False
1 0
2 1
3 2
4 False
5 3
6 False

Btw, Python has a library module for just this kind of thing named bisect.

GrantJ
  • 8,162
  • 3
  • 52
  • 46
2

Though it's too late, it might help someone else :-

def bsearch_helper(arr, key, low, high):
    if low > high:
        return False
    mid = (low + high)//2
    if arr[mid] == key:
        return True
    elif arr[mid] < key:
        return bsearch_helper(arr, key, mid + 1, high)
    else:
        return bsearch_helper(arr, key, low, mid - 1)
    return False

def bsearch(arr, key):
    return bsearch_helper(arr, key, 0, len(arr) - 1)

if __name__ == '__main__':
    arr = [8, 3, 9, 2, 6, 5, 1, 7, 4]
    print (bsearch(sorted(arr), 5))
ravi
  • 10,994
  • 1
  • 18
  • 36
1

You can make use of list slicing too.

def binary_search_recursive(list1, element):
    if len(list1) == 0:
        return False
    else:
        mid = len(list1)//2
        if (element == list1[mid]):
            return True
        else:
            if element > list1[mid]:
                return binary_search_recursive(list1[mid+1:],element)
            else:
                return binary_search_recursive(list1[:mid],element)

However, note that list slicing introduces additional complexity.

  • 1
    Hi Sonal, we can't compare 2 variable mid and element because mid is index and element is value. Line number 6 "if (element == mid)" should be "if (element == list1[mid])" or else you output will be always False. – Lavanya Pant Jul 08 '17 at 08:30
1

There are a lot of solutions here already. Below is one more solution without slicing and that just requires element and list as arguments:

def binary_search(item, arr):
    def _binary_search(item, first, last, arr):
        if last < first:
            return False
        if last == first:
            return arr[last] == item
        mid = (first + last) // 2
        if arr[mid] > item:
            last = mid
            return _binary_search(item, first, last, arr)
        elif arr[mid] < item:
            first = mid + 1
            return _binary_search(item, first, last, arr)
        else:
            return arr[mid] == item

     return _binary_search(item, 0, len(arr) - 1, arr)
print(binary_search(-1, [0, 1, 2, 3, 4, 5]))
michaelrbock
  • 1,160
  • 1
  • 11
  • 20
Vividh S V
  • 131
  • 1
  • 7
1

Recursion Binary Search for sorted list.

The print statements are helpful to see how it all works.

# n = number we are searching for
# lst = the sorted list we are searching in
# sp = list start position
# ep = list end postion
def binary_search_recursion(n: int, lst: list, sp: int = 0, ep: int = None) -> bool:
    # first time searching, start position will be 0
    # and end position will be None
    if ep is None:
        # End position equals total length minus 1 since 0 indexed
        ep = len(lst) - 1

    # get the midpoint of the list (lst)
    mid = (sp + ep) // 2
    mid_item = lst[mid]
    print(f"Start: lst[{sp}] = {lst[sp]}\nMid: lst[{mid}] = {mid_item}\nEnd: lst[{ep}] = {lst[ep]}")
    # If mid item matches the searching number then success
    if mid_item == n:
        print(f"Success!!! Number {n} found in lst[{mid}]")
        return True
    # Else if mid item is greater than number, we eliminate everything to the left and move right
    elif mid_item > n:
        new_ep = mid - 1  
        if new_ep < 0: 
            print(f"Number {n} is too low. Lowest number found is {lst[sp]}")
            return False
        else:
            print(f"Number {n} is less than mid item {mid_item}, change ep {ep} to {new_ep}.\n")
            binary_search_recursion(n, lst, sp, new_ep)
    # Else if mid item is lower than number, we eliminate everything to the right and move left
    elif mid_item < n:
        new_sp = mid + 1
        if new_sp > ep:
            print(f"Number {n} is too High. Highest number found is {lst[ep]}")
            return False
        else:
            print(f"Number {n} is greater than mid item {mid_item}, change sp {sp} to {new_sp}.\n")
            binary_search_recursion(n, lst, new_sp, ep)

Testing out the function:

# A sorted list
num_list = [10,20,30,40,50,60,70,80,90,100,110]

# Search for 10 in num_list
binary_search_recursion(10, num_list)

Start: lst[0] = 10
Mid: lst[5] = 60
End: lst[10] = 110
Number 10 is less than mid item 60, change ep 10 to 4.

Start: lst[0] = 10
Mid: lst[2] = 30
End: lst[4] = 50
Number 10 is less than mid item 30, change ep 4 to 1.

Start: lst[0] = 10
Mid: lst[0] = 10
End: lst[1] = 20
Success!!! Number 10 found in lst[0]

# Search for 110 in num_list
binary_search_recursion(110, num_list)

Start: lst[0] = 10
Mid: lst[5] = 60
End: lst[10] = 110
Number 110 is greater than mid item 60, change sp 0 to 6.

Start: lst[6] = 70
Mid: lst[8] = 90
End: lst[10] = 110
Number 110 is greater than mid item 90, change sp 6 to 9.

Start: lst[9] = 100
Mid: lst[9] = 100
End: lst[10] = 110
Number 110 is greater than mid item 100, change sp 9 to 10.

Start: lst[10] = 110
Mid: lst[10] = 110
End: lst[10] = 110
Success!!! Number 110 found in lst[10]


# Search for 6 in num_list
binary_search_recursion(6, num_list)

Start: lst[0] = 10
Mid: lst[5] = 60
End: lst[10] = 110
Number 6 is less than mid item 60, change ep 10 to 4.

Start: lst[0] = 10
Mid: lst[2] = 30
End: lst[4] = 50
Number 6 is less than mid item 30, change ep 4 to 1.

Start: lst[0] = 10
Mid: lst[0] = 10
End: lst[1] = 20
Number 6 is too low. Lowest number found is 10


# Search for 1111 in num_list
binary_search_recursion(1111, num_list)

Start: lst[0] = 10
Mid: lst[5] = 60
End: lst[10] = 110
Number 1111 is greater than mid item 60, change sp 0 to 6.

Start: lst[6] = 70
Mid: lst[8] = 90
End: lst[10] = 110
Number 1111 is greater than mid item 90, change sp 6 to 9.

Start: lst[9] = 100
Mid: lst[9] = 100
End: lst[10] = 110
Number 1111 is greater than mid item 100, change sp 9 to 10.

Start: lst[10] = 110
Mid: lst[10] = 110
End: lst[10] = 110
Number 1111 is too High. Highest number found is 110
Faiyaz Haider
  • 98
  • 1
  • 11
0

Your first one won't even get started, because list(mid) will immediately raise a TypeError: 'list' object is not callable.

If you fix that (by using list[mid]), your next problem is that you ignore the min and max arguments you receive, and instead set them to 0 and len(list)-1 each time. So, you will infinitely recurse (until you eventually get a RecursionError for hitting the stack limit).

Think about it: the first call to binarySearch(l, 5, 0, 10) recursively calls binarySearch(l, 5, 0, 4). But that call ignores that 4 and acts as if you'd passed 10, so it recursively calls binarySearch(l, 5, 0, 4). Which calls binarySearch(l, 5, 0, 4). And so on.

If you fix that (by removing those two lines), you've got another problem. When you give it the number 10, binarySearch(l, 10, 0, 10) will call binarySearch(l, 10, 6, 10), which will callbinarySearch(l, 10, 8, 10), then binarySearch(l, 10, 9, 10), thenbinarySearch(l, 10, 10, 10). And that last one will check list[10] > element. But list[10] is going to raise an IndexError, because there aren't 11 elements in the list.

And once you fix that off-by-one error, there are no problems left. The problem you asked about cannot possibly ever occur. Here's an example run:

>>> a = range(10)
>>> for i in -3, -1, 0, 1, 4, 5, 9, 10, 11:
...     print i, binarySearch(a, i, 0, 10)
-3 False
-1 False
0 0
1 1
4 4
5 5
9 9
10 False
11 False

Your second version isn't recursive. bSearch never calls bSearch, and that's the whole definition of recursion.

There's nothing wrong with writing an iterative algorithm instead of a recursive algorithm (unless you're doing a homework problem and recursion is the whole point), but your function isn't iterative either—there are no loops anywhere.

(This version also ignores the start and end arguments, but that's not as much of a problem in this case, because, again, you're not doing any recursion.)

Anyway, the only return False in the function is in that first if len(list) == 0. So, for any non-empty list, it's either going to return True, or a number. With your input, it will return 4 for anything less than the value at the midpoint of the list (5), and True for anything else.

abarnert
  • 354,177
  • 51
  • 601
  • 671
0

Your problem here is that you're redeclaring min and max in each loop, so although it should be recursive, passing in a new min or max each time, this isn't in fact happening.

You can solve this by using defaults in the arguments:

def binary_search(list, element, min=0, max=None):
    max = max or len(list)-1

    if max<min:
        return False
    else:
        mid= min + (max-min)/2

    if mid>element:
        return binary_search(list, element, min, mid-1)
    elif mid<element:
        return binary_search(list, element, mid+1, max)
    else:
        return mid

If you're not familiar with the syntax on line 2, max = max or len(list)-1 max will be set to len(list)-1 only if max is not passed in to the method.

So you can call the method simply using:

binary_search(range(10), 7)
# Returns 7

binary_search(range(10), 11)
# Returns False
sherwoor
  • 185
  • 6
  • This solution doesn't index the list. Try this test case: for val in range(7): print(val, binary_search(val, [1, 2, 3, 5])) – GrantJ Nov 14 '13 at 23:06
  • @GrantJ You're right: I assumed a sequential list starting from zero, as you would get from range(10) but yours is a better answer. – sherwoor Nov 14 '13 at 23:22
0

Just another answer to the same question:

def binary_search(array, element, mini=0, maxi=None):
  """recursive binary search."""

  maxi = len(array) - 1 if maxi is None else maxi

  if mini == maxi:
    return array[mini] == element
  else:
    median = (maxi + mini)/2
    if array[median] == element:
      return True
    elif array[median] > element:
      return binary_search(array, element, mini, median)
    else:
      return binary_search(array, element, median+1, maxi)

print binary_search([1,2,3],2)
Gluamice
  • 71
  • 1
  • 4
0

I made this one. Correct me if there's any bug.

import math

def insert_rec(A,v,fi,li):

    mi = int(math.floor((li+fi)/2))

    if A[mi] == v:
       print("Yes found at: ",mi)
       return

    if fi==li or fi>li:
       print("Not found")
       return

    if A[mi] < v:
       fi = mi+1
       insert_rec(A,v,fi,li)

    if A[mi] > v:
       li = mi-1
       insert_rec(A,v,fi,li)
CASE
  • 43
  • 8
0
def bs(list,num):    #presume that the list is a sorted list
#base case
    mid=int(len(list)/2)          # to divide the list into two parts
    if num==list[mid]:
         return True
    if len(list)==1:
       return False
#recursion
    elif num<list[mid]:           #if the num is less than mid
        return bs(list[0:mid],num)    #then omit all the nums after the mid
    elif num>list[mid]:           #if the num is greater than mid
        return bs(list[mid:],num)     # then omit all the nums before the mid
#return False
list=[1,2,3,4,5,6,7,8,9,10]
print(bs(list,20))
<<< False
 print(bs(list,4))
<<< True
Shane FAN
  • 29
  • 7
  • Thank you for this code snippet, which might provide some limited short-term help. A proper explanation [would greatly improve](//meta.stackexchange.com/q/114762) its long-term value by showing *why* this is a good solution to the problem, and would make it more useful to future readers with other, similar questions. Please [edit] your answer to add some explanation, including the assumptions you've made. – Toby Speight May 16 '18 at 16:55
0

You can implement binary search in python in the following way.

def binary_search_recursive(list_of_numbers, number, start=0, end=None):

    # The end of our search is initialized to None. First we set the end to the length of the sequence.
    if end is None:
        end = len(list_of_numbers) - 1

    if start > end:
        # This will happen if the list is empty of the number is not found in the list.
        raise ValueError('Number not in list')

    mid = (start + end) // 2  # This is the mid value of our binary search.

    if number == list_of_numbers[mid]:
        # We have found the number in our list. Let's return the index.
        return mid

    if number < list_of_numbers[mid]:
        # Number lies in the lower half. So we call the function again changing the end value to 'mid - 1' Here we are entering the recursive mode.



        return binary_search_recursive(list_of_numbers, number, start, mid - 1)
    # number > list_of_numbers[mid]
    # Number lies in the upper half. So we call the function again changing the start value to 'mid + 1' Here we are entering the recursive mode.

    return binary_search_recursive(list_of_numbers, number, mid + 1, end)

We should check our code with good unittest to find loop holes in our code.

Hope this helps you.

Gurupratap
  • 773
  • 10
  • 11
0

Here is My Recursion Solution of Binary Search

def recBinarySearch(arr,ele):
    if len(arr) == 0:
        return False
    else:
        mid = len(arr)/2

        if arr[mid] == ele:
            return True
        else:
            if ele < arr[mid]:
                return recBinarySearch(arr[:mid], ele)
            else:
                return recBinarySearch(arr[mid+1], ele)
0

You can do it this way as well:

def recursive_binary_search(list, item):
  """find the index of the given item in the list recursively"""
  low = 0
  high = len(list) - 1
  if low <= high:
    mid = low + high
    guess = list[mid]
    if guess == item:
      return mid
    if guess > item: # item must be in the first split
      return recursive_binary_search(list[low:mid], item)
    else: # check in second split otherwise
      return recursive_binary_search(list[mid:high], item)
  return None

def main():
  print(recursive_binary_search([2,3,4,5,6,7,8], 3)) #  will print 1

if __name__ == "__main__":
  main()
Random Forest
  • 11
  • 1
  • 4