Binary Search with Python through recursion

Question

I have written this code for binary search in python.

import math
import copy
def binarySearch(array, target):
    c=-1
    flag=False
    org_array=copy.deepcopy(array)
    # Write your code here.
    l=array[0:math.floor(len(array)/2)]
    r=array[math.floor(len(array)/2):len(array)]
    for i in r:
        if(i==target):
            flag=True
            c=org_array.index(i)
            
            return c
    if(flag==False):
        array=l
        binarySearch(array, target)
    
        
        
binarySearch([0,1,21,33,45,45,61,71,72,73,74], 21)

Though it is working fine and returning index for elements in 'r'(second half of list), but it is not returning anything for search element in first half of list-->(l).May i know, where i am going wrong.

Your "left" part doesn't return anything. Also, the "right" part is not recursive, it iterates on the second sublist — gimix
– gimix, Commented Oct 26, 2022 at 6:16

Ashutosh Yadav · Accepted Answer · 2022-10-26 07:10:50Z

The Code you have written is not a Binary Search.

Here is what you are doing.

array and target are given.

array = [0,1,21,33,45,61,71,72,73,74]

target = 21

You are splitting the array into two parts.

l = [[0,1,21,33,45] ; r = [61,71,72,73,74]
Now you are performing a liner search in r array. you are iterating in array r using for loop and checking for the target. If the value in for loop matches the target you are returning the index of that element.
If you are not getting the target value in r array. you are calling the binarySearch() function and passing l array and the target in it. and again the same procedure goes on.

NOTE:: Even though it is not a Binary search it is working fine. It is kind of a linear search. here are some examples:

--> binarySearch([0, 1, 21, 33, 45, 45, 61, 71, 72, 73, 74], 71)

|_ output: 7

--> binarySearch([0, 1, 21, 33, 45, 45, 61, 71, 72, 73, 74], 74)

|_ output: 10

--> binarySearch([0, 1, 21, 33, 45, 45, 61, 71, 72, 73, 74], 0)

|_ output: 0

--> binarySearch([0, 1, 21, 33, 45, 45, 61, 71, 72, 73, 74], 45)

|_ output: 4

MUST NOTE THIS:: If you are using this algorithm and let's say the array size is huge. let's say 10^99999 if you will split the array into two equal parts and iterate into any sub-array. It will be basically a linear search.

Here you can find how to perform Binary Search (Recursive and Iterative)

Alexander · Accepted Answer · 2022-10-26 07:11:54Z

In binary search the goal is to return the index of the target in the array.

So right off the bat you are making a mistake by splitting the array into halves because any index you find in the half won't necessarily be the same index to the original array plus making copies of arrays is not cheap and binary search is supposed to be efficient.

Next issue is your for loop, there shouldn't be any for loops in a recursive binary search algorithm, not only that but once you find the correct element you use the .index method which internally runs a for loop. And if using the index method were the right call then you could simply call orig_array.index(target) and be done.

Here is an example of how you could write a binary search algorithm in python, I even kept the functions signature the same just in case that is a requirement for some reason.

def binarySearch(array, target):
    start, end = 0, len(array) - 1

    def search(start, end):
        l = (end - start)//2 + start
        if start < end:
            if array[l] == target:
                return l
            elif target < array[l]:
                return search(start, l)
            else:
                return search(l+1,end)
        return -1
    return search(start, end)


print(binarySearch([0,1,21,33,45,45,61,71,72,73,74], 78))
print(binarySearch([0,1,21,33,45,45,61,71,72,73,74], -1))
print(binarySearch([0,1,21,33,45,45,61,71,72,73,74], 2))
print(binarySearch([0,1,21,33,45,45,61,71,72,73,74], 72))
print(binarySearch([0,1,21,33,45,45,61,71,72,73,74], 21))

output:

-1
-1
-1
8
2

Collectives™ on Stack Overflow

Binary Search with Python through recursion

2 Answers 2

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Related