Recursive binary search in Python

Question

I have a list with numbers from 0 to 9:

mylist = list(range(10))

I get 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 return binary_search(mylist, element, mymin, mid-1)?

Answer 1

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

Answer 2

The first solution does not look right because it does not index the list.

This problem also spurred me the first time I wrote a solution, so be sure to check your algorithm.

Here is 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 right:

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 , bisect.

Answer 3

.

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)

, .

Answer 4

. , :

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]))

Answer 5

,

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

Answer 6

, list(mid) TypeError: 'list' object is not callable.

( list[mid]), , min max, , 0 len(list)-1 . , ( , RecursionError ).

: binarySearch(l, 5, 0, 10) binarySearch(l, 5, 0, 4). 4 , 10, binarySearch(l, 5, 0, 4). binarySearch(l, 5, 0, 4). .

( ), . 10, binarySearch(l, 10, 0, 10) binarySearch( l, 10, 6, 10) , which will call binarySearch (l, 10, 8, 10), binarySearch( l, 10, 9, 10) , then binarySearch (l, 10, 10, 10)), list[10] > element. list[10] IndexError, 11 .

, . , , . :

>>> 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

---

. bSearch bSearch .

( , - ), : .

( start end, , , , .)

, return False if len(list) == 0. , True, . 4 - , (5), True - .

Answer 7

, min max , , , min max, .

, :

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

2,   max = max len (list) -1 max len (list) -1, max .

, :

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

binary_search(range(10), 11)
# Returns False

Answer 8

:

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)

Answer 9

. , .

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)

Answer 10

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

Answer 11

Python .

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

unittest, .

, .

Answer 12

, :

1) , . - .

2) 2 : (, ) 4 , / (/) , .

3) , .

# 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)

Answer 13

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)

Answer 14

, - : -

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