Binary Search Error while trying to search through list

Question

def quickSort(arr):
  if len(arr) <= 1:
    return arr
  pivot = arr[int(len(arr)/2)]
  left = [x for x in arr if x < pivot]
  middle = [x for x in arr if x == pivot]
  right = [x for x in arr if x > pivot]
  return quickSort(left) + middle + quickSort(right)

def binSearch(sorted_arr, target):
  cen = int(len(sorted_arr)/2)
  if sorted_arr[cen] == target:
    return cen
  elif sorted_arr[cen] < target:
    return binSearch(sorted_arr[0:cen], target)
  else: 
    return binSearch(sorted_arr[cen:len(sorted_arr)], target)

my_array = [11, 9, 12, 7, 3, 8, 10, 2, 5, 1, 4, 6]
result = binSearch(quickSort(my_array), 13)
if result == -1:
  print("Element not found")
else:
  print(f"Element found at index {result}")

This is my code and this is the error I am encountering...

line 12, in binSearch
  if sorted_arr[cen] == target:
IndexError: list index out of range

Now I know what that error means. It is just that I don't understand how I am encountering this error. I tried to visualize it myself and it turns out perfectly fine!

Answer 1

Your quicksort function is fine, let me fix the binary search, my code returns the correct index value:

def binSearch(sorted_arr, target, left=0):
  if len(sorted_arr) == 0:
    return -1
  cen = len(sorted_arr) // 2
  if sorted_arr[cen] == target:
    return left + cen
  elif sorted_arr[cen] < target:
    return binSearch(sorted_arr[cen+1:], target, left + cen + 1)
  else:
    return binSearch(sorted_arr[:cen], target, left)

Answer 2

Basically in your binary search function you didn't provide a terminating statement. It keeps on dividing your array in half. You have to provide a terminating statement to check if the length of your array is 0.

if len(sorted_arr) == 0:
    return -1

Check here for more information on binary search

Answer 3

Your implementation of a recursive binary search is flawed.

Here's an improvement:

def binSearch(_list, _item):
    def _binSearch(_list, lo, hi):
        nonlocal _item
        if hi >= lo:
            mid = (hi + lo) // 2
            if _list[mid] == _item:
                return mid
            elif _list[mid] > _item:
                return _binSearch(_list, lo, mid - 1)
            else:
                return _binSearch(_list, mid + 1, hi)
        return -1
    if _list and _item >= _list[0] and _item <= _list[-1]:
        return _binSearch(_list, 0, len(_list)-1)
    return -1

With this version you just call it with the (sorted) list and the item you're looking for.

However, a recursive binary search will almost always be slower than an iterative approach such as:

def binSearch(slist, item):
    if slist and item >= slist[0] and item <= slist[-1]:
        lo = 0
        hi = len(slist) - 1
        while lo <= hi:
            m = (lo + hi) // 2
            mv = slist[m]
            if mv == item:
                return m
            if mv < item:
                lo = m + 1
            else:
                hi = m - 1
    return -1

And if you're looking for optimum performance then I suggest:

from bisect import bisect_left

def binSearch(slist, item):
    if slist and item >= slist[0] and item <= slist[-1]:
        i = bisect_left(slist, item)
        if i != len(slist) and slist[i] == item:
            return i
    return -1