3
\$\begingroup\$

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

```
\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

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')
```
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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