Does my Binary Search implementation work at its best performance ? ( Have I implemented it correctly ? )

Question

https://code.sololearn.com/cc6ed8JnDKQW/?ref=app

Answer 1

hm, that's interesting!
i googled the geeksforgeeks implementation, and its significant difference is using indexes instead of creating a new array every time recursive call is done. i didn't think about it at all, but this case proves that accessing an array by index is way faster than allocating memory for a new array.
fun fact is that I did encounter this before, when I've implemented another algorithm in C++ using vectors (it is somewhat similar to python lists), and then rewritten it for arrays and pointers, storing indexes of the 1st and last elements. it became MUCH faster then

Answer 2

thanks! and it still doesn't work?

btw Jayakrishna is right, taking [mid + 1:] instead of [mid:] is really better bc it excludes the already checked element at [mid] and reduces number of potential recursive calls, I didn't get that before, sorry

Answer 3

query elements are not in sorted..!
It's confusing.. But i think, bilorplate code already given so better no bother now..
Yes. Indexing approach is more faster.. But taking new list every time is increases space complexity more.
Hope it solved..

Answer 4

Avinesh Perhaps it's because each list takes O(k) to be sliced, and as I used it in my program, it may take some extra time to do the process.

Answer 5

Jayakrishna🇮🇳 the problem is not that it doesn't give the correct answer, but it's of time complexity. In some cases, it takes more than O(logn) to output.

Answer 6

i tested it on a really big list, it works perfectly fine:

>> arr = list(range(1000000))
>> print(Search(arr, 22))
1

and don't change mid to mid+1, it will divide the list incorrectly missing the middle element

im curious why your checking system says something is wrong. is it in sololearn? could you share a link if possible?

Answer 7

I mean where are you trying this..?
Sololearn won't give Time Limit error.
And you said "judge system raise error". If we access the test then we may try the correct solution or may find problem with your code.

Answer 8

Patrick Jayakrishna🇮🇳
I'm sorry to say this friends, but this is a private course, others are not allowed to have access to the judge system.
I just checked out a test case that my program doesn't pass.
It has 10000 numbers with 10000 queries.
The first line is the numbers, and the next 10000 lines are queries. For example :
10000 10000
4828, 63728, 372938, 1039382838, 0, ..., 27361 # numbers
? 5 # query lines - number 1
? 338 # number 2
...
? 3728 # number 10000
For each query, I should output whether the number is found in the given numbers or not.

Answer 9

Patrick Jayakrishna🇮🇳 I see, thanks for your answers friends :)

Answer 10

Yes,
I edit this code with proof
check out now:
https://code.sololearn.com/c2MK3IEEPgm3/?ref=app

Answer 11

Yes you have implemented it correctly and it works fine. You can test for yourself using something like below.

arr = [1,2,3,4,5,6]
res = Search(arr,5)
print(res)

Answer 12

Avinesh it does give correct answer, but a judge system says that it cannot pass test cases. It raises Time Limit Error

Answer 13

Ali_combination
return search( arr[mid+1:], item)

This way taking mid+1 skips one more element. It's reduse time needed.
Ok. It's need some more modifications that instead of checking len(arr) == 1, only continue below steps when list is not empty. So you can remove, first 4lines of if block.

Answer 14

Patrick (do you have access to my source code ?)
not really sure ... but it could be down to different reasons, unstable internet connection, or a technical flaw in Sololearn. I used to have this problem too :(

and yes, I have it in my code bits, the link is just this :
https://code.sololearn.com/cc6ed8JnDKQW/?ref=app

Answer 15

It's not incorrect solution. It's work fine for binary search. But It's about time complexity issue as per OP question.
Yes. Change of mid+1 goes to check arr[0] even when list is empty so raise error. And it need to avoid in OP code. The way I mentioned in my reply..
I expect for large list there exist difference skipping atleast 1 element also.
But again that's my guess. Original complete task checking may help to find problem I think.

Answer 16

Ali_combination
What is judge system for your task?

Answer 17

Jayakrishna🇮🇳 you mean you want to see the judge system ?

Answer 18

Ali_combination I meant the link to the judge system, I'd like to see it
I accessed your source code and tested it with lines I posted above

Answer 19

Patrick no it didn't pass test cases.
well yeah ... it'll work faster then ... but it doesn't give it any especial impetus. By the way, I used another binary search implementation, from Geeks For Geeks website and gave it a large input. Then I used time module to measure how much time it takes to pass the test. Next time, I did the same but instead of Geeks For Geeks's implementation, I used mine and timed it too. Finally, the two results are like 0.000004 and 0.00008 respectively. The difference between the two are somewhat significant.

Answer 20

'''
Ali_combination try this:
1.use iteration instead of recursion.
2.modify your middle formula
This algorithm was derived from
https://realpython.com/binary-search-JUMP_LINK__&&__python__&&__JUMP_LINK/
'''
def Search(arr, item):
left, right = 0, len(arr) - 1

while left <= right:
middle = left + (right - left) // 2

if arr[middle] == item:
return 1

if arr[middle] < item:
left = middle + 1
elif arr[middle] > item:
right = middle - 1
return 0