using binary search to return index of target

binary search program in c++
binary search python
binary search return index python
binary search return index java
binary search pseudocode
binary search example step by step
binary search time complexity
binary search calculator

I have to return the index of the target element of an array.

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

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

The idea of binary search is to use the information that the array is sorted and reduce the time If x matches with middle element, we return the mid index. Else If  Given a sorted array of integers and a target value, find out if a target exists in the array or not in O(log(n)) time using Binary Search Algorithm in C and Java. Binary Search is a divide and conquer algorithm. Like all divide and conquer algorithms, Binary Search first divides a large array into two smaller subarray

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+len(aList[: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.

The output is the index in array of target : Let min = 0 Let's start by figuring out what index the binarySearch function should return in this case. It should be a  In its simplest form, binary search is used to quickly find a value in a sorted sequence (consider a sequence an ordinary array for now). We’ll call the sought value the target value for clarity. Binary search maintains a contiguous subsequence of the starting sequence where the target value is surely located. This is called the search space. The search space is initially the entire sequence.

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

A binary search can only be used if the data is sorted. It compares the value at the middle index with the target value (the value you are return middle;. 19. In normal binary search, we return as soon as we find any occurrence of the given target element in it. In order to find the first occurrence of the element, the idea is to modify the normal binary search in such a way that we do not stop the search as soon we find any occurrence of the target element.

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

Binary search begins by comparing an element in the middle of the array with the target value. If the target value matches the element, its position in the array is  Remember the first position is index 0. 18, 17, 15; Remember binary search starts in the middle and halves the list. 14, 17, 15; Looks like you might be off by one, be careful that you are calculating the midpont using integer arithmetic. 12, 17, 15; Binary search starts at the midpoint and halves the list each time. It is done when the list is empty.

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(log2 N).
  2. If the given list is not sorted then we need to sort the list at the beginning only

Given a sorted array and a target value, return the index if the target is found. LeetCode – Search Insert Position (Java) This is a binary search problem. Since the Binary Search will finish after the first "find" of a particular value. I was thinking of doing a Binary Search for finding x in the sorted array, and then checking all values before and after this index, but then if the array contained all x values, it doesn't seem like it would be that much better.

If the target value was not present in the sequence, binary search would empty Since each comparison binary search uses halves the search space, we can A and a target value, return the index of the first element in A equal to or greater  1. here is a modified binary search code in JAVA with time complexity O (logn) that : returns index of element to be searched if element is present. returns index of next greater element if searched element is not present in array. returns -1 if an element greater than the largest element of array is searched.

The algorithms return the index of some element that equals the given value (if there are multiple such elements, it returns some arbitrary initially called with low = 0, high = N-1 BinarySearch(A[0. we've found our target Exponential search extends binary search to unbounded lists. It starts by finding the first element with an index that is both a power of two and greater than the target value. Afterwards, it sets that index as the upper bound, and switches to binary search.

indexOf – returns first index of element, or -1 if not found. contains - returns true binary search: Locates a target value in a sorted array or list by successively  Binary Search: Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half.

Comments
  • 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?
  • 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.