How do I return the index of the target element in a Python array?

Question

Currently, when I search for the element that is at the midpoint it returns the correct index, but for any other element it does not work for me.

I think I am making a mistake when I split the array:

    aList = [1,3,5,6,8,9,10,12,34,56,78,456]
    def recursiveBinarySearch(aList, target):
        #aList = sorted(aList)
        
        if len(aList) == 0:
            return False
        else:
            midpoint = len(aList) // 2
            if aList[midpoint] == target:
                return aList.index(target)
            else:
                if target < aList[midpoint]:
                    return recursiveBinarySearch(aList[:midpoint],target)
                else:
                    return recursiveBinarySearch(aList[midpoint+1:],target)
    
    print(recursiveBinarySearch(aList,9))

Chrisse

is it possible that when I find the element the array is only that element due to the nature of the binary search splitting the array in half? – Chrisse

Answer 1

That is because every time you make a recursive call, a different modified list is passed and the index will change in every call. For example, if you search for a number in second half of the array, the final returned value will be less than len(aList)/2 because only this part of the array will be passed in the next iteration.

The workaround is to pass start and end points of the list instead of splitting the list.

aList = [1,3,5,6,8,9,10,12,34,56,78,456]
def recursiveBinarySearch(aList, target, start, end):
    #aList = sorted(aList)

    if end-start+1 <= 0:
        return False
    else:
        midpoint = start + (end - start) // 2
        if aList[midpoint] == target:
            return midpoint
        else:
            if target < aList[midpoint]:
                return recursiveBinarySearch(aList, target, start, midpoint-1)
            else:
                return recursiveBinarySearch(aList ,target, midpoint+1, end)

print(recursiveBinarySearch(aList,455, 0, len(aList)))

Rudiger

Your answer fails with an IndexError when asked to find a value greater than one that is not in the list. I have edited your answer to fix the problem, as well as edited your args to be kwargs so we don't have to pass them in every time we call the function. – Lawrenson

Answer 2

Your algortihm gives the index in the last splitted list. So for your answer if you would print the list for 9, we would get the following:

[1, 3, 5, 6, 8, 9, 10, 12, 34, 56, 78, 456]
[1, 3, 5, 6, 8, 9]
[8, 9]

Wich returns the index 1. which is correct for the last list [8, 9]. This can easely be fixed by remebering the length of list.

aList = [1,3,5,6,8,9,10,12,34,56,78,456]
def recursiveBinarySearch(aList, target, index):
    #aList = sorted(aList)
    
    if len(aList) == 0:
        return False
    else:
        midpoint = len(aList) // 2

        if aList[midpoint] == target:
            return aList.index(target)+index
        else:
            if target < aList[midpoint]:
                return recursiveBinarySearch(aList[:midpoint],target, index)
            else:
                 return recursiveBinarySearch(aList[midpoint:],target, index + midpoint)
                

print(recursiveBinarySearch(aList,56,0))

This uses a bit less memory than the previous solution. And ofcourse this is also faster, although that is marginal.

Unbated

Answer 3

Tried editing the accepted answer because it fails when searching for numbers that are higher than those in the list but for some reason the OP did not accept the edits, meaning that answer is still wrong. That being the case, I will post the answer here. Not only does this answer fix the IndexError when asked to find a value greater than one that is not in the list, it also changes the args to be kwargs so we don't have to pass them in every time we call the function

aList = [-1,1,3,5,6,8,9,10,12,34,56,78,456] 

def binary_search(arr,item,low = 0, high = None):
    if high == None:
        high = len(arr)
    mid = low + (high-low) //2  
    if high - low + 1 <= 0 or mid==high:
        return False
    else:
        guess = arr[mid]
        if guess == item:
            return mid
        if item < guess:
            return binary_search(arr, item, low, mid)
        else:
            return binary_search(arr, item, (mid+1), high)

(binary_search(aList,457))

Lawrenson

Answer 4

I just wanted to share my solution to this problem, it seems a little bit simpler:

def binary_search(array, value):
    index = int(len(array)/2) -1
    end = int(len(array)) - 1
    while array[index] != value:
        if index == end:
            return None
        elif array[index] > value:
            end = index
            index = int(index/2)
        elif array[index] < value:
            index = int((index+1 + end)/2)
    return index

Rem

Answer 5

Solution with detailed explanation

binary search reduces the number of iteration to search an item in List. We have to first initialize the first index as 0 and last index as the length of the list - 1. Then we will select the middle element as (first + last)//2 Now we have to compare the value at the middle element with the query element.

1. If it equals the middle element then we can return its index as it is.
2. If the query element is less than the middle element then we'll update the last element as mid-1. (so that we have to iterate the only first part of the list)
3. If the query element is greater than the middle element then we'll update the first element as mid+1. (so that we have to iterate the only second part of the list)

Below code snippet will give a clear picture of the above statements.

aList = [-1,1,3,5,6,8,9,10,12,34,56,78,456] 

def binarySearch(numbers,item):
    first = 0 # first index
    last= len(numbers)-1 #last index
    found = False
    while( first<=last and not found):
        mid = (first + last)//2
        if numbers[mid] == item:
            found = True
            return mid
        else:            
            if item < numbers[mid]:
                last = mid - 1
            else:
                first = mid + 1 

print(binarySearch(aList,456))

NOTE :

1. As we dispose off one part of the search case during every step of binary search and perform the search operation on the other half, this results in the worst-case time complexity of O(log₂ N).
2. If the given list is not sorted then we need to sort the list at the beginning only

Allwein

Answer 6

Below is my solution.

Check out this visualization. (There's a coded solution there too!)

def binary_search(input_array, value):

    low = 0
    high = len(input_array) - 1

    while low <= high:
        mid = (low + high) / 2
        if input_array[mid] == value:
            return mid
        elif input_array[mid] < value:
            low = mid + 1
        else:
            high = mid - 1

    return -1

'''

Thigmotaxis

Answer 7

A little bit trimmed down version of @Gijs Den Hollander's code. The conditionals are simplified and midpoint is used instead of len(aList[:midpoint]) like I pointed out in the comment:

def binarySearch(array, target, index=0):
    midpoint = len(array) // 2
    if array[midpoint] == target:
        return index + midpoint
    elif len(array) < 2:
        return -1
    else:
        return binarySearch(array[:midpoint], target, index) if target < array[midpoint] else binarySearch(array[midpoint:], target, midpoint+index)

Nikos

Answer 8

Another simple method can be done,

def find_index(input_list, target, sorted=False):
    print('Input list: {}'.format(input_list))

    if sorted:
        input_list.sort()
        print('Sorting Input list: {}'.format(input_list))

    try:
        index = input_list.index(target)
    except ValueError as e:
        print(e)
        index = None

    return index

And for the binary search method,

def bsearch(il, x):
    """binary search for an input list (il)"""
    il.sort()
    print('Input list is: {}'.format(il))

    l = len(il)
    m = round(l/2)

    n = il[m]
    print("m is {} and n is {}".format(m, n))

    if n == x:
        msg = 'The number "{}" found in list index "{}"'.format(x, m)
        print(msg)
        return x
    elif x < n:
        nl = il[:m]
    elif x > n:
        nl = il[m+1:]
    elif m < 1:
        return None

    return bsearch(nl, x)

Nutcracker