Python Binary Search

Question

My take on a binary search algorithm without research or knowledge of an efficient one. It would be appreciated if one could show me an efficient way to do it using recursion or a more pythonic approach.

from math import *

numList = [i for i in range(11)]

while True:
     try:
           beginning = 0
           end = len(numList) - 1
           mid = floor(((end-beginning)/2) + beginning)

           value = int(input("What value would you like to search for?: "))

           notFound = True

           while notFound:
               if value > end or value < beginning:
                   print("The value is not in the list")
                   break
               elif value == mid:
                   print("The value is in the list")
                   print("The index is " + str(mid))
                   notFound = False
               elif value == end:
                   print("The value is in the list")
                   print("The index is " + str(end))
                   notFound = False
               elif value > mid:
                  beginning = mid
                  mid = floor(((end-beginning)/2) + beginning)
               elif value < mid:
                  end = mid
                  mid = floor(((end-beginning)/2) + beginning)
     except ValueError:
          print("Invalid characters")

```

kyticka · Accepted Answer · 2020-05-06 09:17:29Z

numList is not used (this is "ok" as numList[i] == i). There is value == mid or value == end several times. But this just means you are comparing a value to be found with an index. The correct way would be value == numList[mid].

Consider using a function that does the binsearch for you.

You may or may not use recursion. There is a nice way to do binsearch without recursion.

I have also incorporated some naming conventions of python. If you are interested try programs like pylint. I have also added a bit nicer string formatting and some other python features you can live without but can come handy.

"""Binary search."""
from random import randint

def bin_search(sorted_list, to_find):
    """Searches the sorted_list for a to_find.
    If the to_find is found return (True, index)
    Otherwise return (False, 0)
    """
    beg = 0
    end = len(sorted_list) - 1
    while beg <= end:
        mid = (end + beg) // 2  # integer division
        if sorted_list[mid] == to_find:
            return (True, mid)
        if sorted_list[mid] < to_find:
            (beg, end) = (mid + 1, end)
        else:  # sorted_list[mid] > to_find
            (beg, end) = (beg, mid - 1)
    return (False, 0)

# Create a sorted list of random numbers
MY_LIST = sorted(randint(0, 100) for _ in range(20))
print(MY_LIST)

while True:
    try:
        TO_FIND = int(input('Enter value you want to find: '))
        (FOUND, INDEX) = bin_search(sorted_list=MY_LIST, to_find=TO_FIND)
        if FOUND:
            print(f'Found {TO_FIND} at index: {INDEX}!')
        else:
            print(f'Value {TO_FIND} not found!')
    except ValueError:
        print('Invalid number to find')
```

Stack Exchange Network

Python Binary Search

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Python Binary Search

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions