i made the following binary search algorithm, and I am trying to improve it. suggestions?

Question

i am doing a homework assignment where I have to check large lists of numbers for a given number. the list length is <= 20000, and I can be searching for just as many numbers. if the number we are searching for is in the list, return the index of that number, otherwise, return -1. here is what I did.

i wrote the following code, that outputsthe correct answer, but does not do it fast enough. it has to be done in less than 1 second.

here is my binary search code:`I am looking for suggestions to make it faster.

def binary_search(list1, target):
  p = list1
  upper = len(list1)
  lower = 0
  found = False
  check = int((upper+lower)//2)
  while found == False:
    upper = len(list1)
    lower = 0    
    check = int(len(list1)//2)
    if list1[check] > target:
      list1 = list1[lower:check]
      check= int((len(list1))//2)
    if list1[check] < target:
      list1 = list1[check:upper]
      check = int((len(list1))//2)
    if list1[check] == target:
      found = True
      return p.index(target)
    if len(list1)==1:
      if target not in list1:
        return -1`

grateful for any help/

Answer 1

The core problem is that this is not a correctly written Binary Search (see the algorithm there).

There is no need of index(target) to find the solution; a binary search is O(lg n) and so the very presence of index-of, being O(n), violates this! As written, the entire "binary search" function could be replaced as list1.index(value) as it is "finding" the value index simply to "find" the value index.

The code is also slicing the lists which is not needed¹; simply move the upper/lower indices to "hone in" on the value. The index of the found value is where the upper and lower bounds eventually meet.

Also, make sure that list1 is really a list such that the item access is O(1).

(And int is not needed with //.)

---

¹ I believe that the complexity is still O(lg n) with the slice, but it is a non-idiomatic binary search and adds additional overhead of creating new lists and copying the relevant items. It also doesn't allow the correct generation of the found item's index - at least without similar variable maintenance as found in a traditional implementation.

Answer 2

Try using else if's, for example if the value thats being checked is greater then you don't also need to check if its smaller.