The function doen't iterate over the whole array

Question

I have the following code which gets two arrays and finds the location of each item in the second array based on the first array. For example, for 23 from loc1, which is between 20 and 25 in array it should return 20.

matrix_x = []
def binarySearch(alist, loc):
    for item in loc:
        midpoint = len(alist)//2
        if midpoint == 1:
            if item<alist[midpoint]:
                return matrix_x.append(alist[midpoint-1])
            else:
                return matrix_x.append(alist[midpoint])         
        else:
            if item<alist[midpoint]:
                return binarySearch(alist[:midpoint],loc)
            else:
                return binarySearch(alist[midpoint:],loc)
    return matrix_x

array = [5,10,15,20,25]
loc1= [23,7,11]

print(binarySearch(array, loc1))
print(matrix_x)

I expect to receive this array as the result:

[20,5,10]

But I receive only the first item like this:

[20]

remove the `return` keyword by using the return statement you end the script execution. — Amr Aly, Jan 30 '18 at 23:19
Your algorithm is questionable as it combined two very different features into a single function; my recommendation is to decouple the two, first being the recursive `binarySearch` into its own thing that takes the list and __one__ location, the other being the iteration through the list of locations and passing that to the decoupled `binarySearch` function. — metatoaster, Jan 30 '18 at 23:20

score 2 · Answer 1 · answered Jan 30 '18 at 23:17

2

You're returning the matrix_x.append statement, so it only ever appends 1 item, in this case 20. To get the behavior you want, you may need to restructure your function some.

answered Jan 30 '18 at 23:17

SuperStew

2,857
2
15
27

Mike Müller · Accepted Answer · 2018-01-30T23:39:59.083

1

Just use the bisect module:

import bisect

def binarySearch(alist, loc):
    return [alist[bisect.bisect(alist, i) - 1] for i in loc]

array = [5,10,15,20,25]
loc1= [23,7,11]
print(binarySearch(array, loc1))

Output:

[20, 5, 10]

Finding the index is simpler:

def binarySearchIndex(alist, loc):
    return [bisect.bisect(alist, i) - 1 for i in loc]

edited Jan 30 '18 at 23:39

answered Jan 30 '18 at 23:27

Mike Müller

82,630
20
166
161

Thanks it works. Your solution is the best! Do you know how can we get the index of each item instead of the item itself? For example, in this question, it should give me [4, 0, 1]. – Mahsa Jan 30 '18 at 23:37
1

Updated my answer. – Mike Müller Jan 30 '18 at 23:40
1

Great that it helped. BTW, you have the privilege to [upvote](http://stackoverflow.com/help/privileges/vote-up). ;) – Mike Müller Jan 30 '18 at 23:41
Thanks. I receive this error: IOPub data rate exceeded. – Mahsa Jan 30 '18 at 23:42
My actual dataset is really huge. It has more than 5000 records. Does this function work for such a big dataset too? – Mahsa Jan 30 '18 at 23:44
1

This is problem with [Jupyter Notebook](https://stackoverflow.com/questions/43288550/iopub-data-rate-exceeded-when-viewing-image-in-jupyter-notebook). – Mike Müller Jan 30 '18 at 23:45
5000 should be no problem. – Mike Müller Jan 30 '18 at 23:47

The function doen't iterate over the whole array

2 Answers2