+ 2

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

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

2nd Sep 2022, 2:00 PM
Ali_combination
Ali_combination - avatar
21 Réponses
+ 5
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
3rd Sep 2022, 5:33 PM
Patrick
Patrick - avatar
+ 3
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
3rd Sep 2022, 4:05 PM
Patrick
Patrick - avatar
+ 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..
3rd Sep 2022, 6:49 PM
Jayakrishna 🇮🇳
+ 2
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.
3rd Sep 2022, 7:48 AM
Ali_combination
Ali_combination - avatar
+ 2
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.
3rd Sep 2022, 11:25 AM
Ali_combination
Ali_combination - avatar
+ 2
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?
3rd Sep 2022, 2:16 PM
Patrick
Patrick - avatar
+ 2
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.
3rd Sep 2022, 3:15 PM
Jayakrishna 🇮🇳
+ 2
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.
3rd Sep 2022, 3:32 PM
Ali_combination
Ali_combination - avatar
+ 2
Patrick Jayakrishna🇮🇳 I see, thanks for your answers friends :)
4th Sep 2022, 5:23 AM
Ali_combination
Ali_combination - avatar
+ 2
Yes, I edit this code with proof check out now: https://code.sololearn.com/c2MK3IEEPgm3/?ref=app
4th Sep 2022, 9:05 AM
filibuster
filibuster - avatar
+ 1
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)
2nd Sep 2022, 6:29 PM
Avinesh
Avinesh - avatar
+ 1
Avinesh it does give correct answer, but a judge system says that it cannot pass test cases. It raises Time Limit Error
3rd Sep 2022, 3:37 AM
Ali_combination
Ali_combination - avatar
+ 1
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.
3rd Sep 2022, 11:56 AM
Jayakrishna 🇮🇳
+ 1
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
3rd Sep 2022, 2:38 PM
Ali_combination
Ali_combination - avatar
+ 1
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.
3rd Sep 2022, 2:41 PM
Jayakrishna 🇮🇳
+ 1
Ali_combination What is judge system for your task?
3rd Sep 2022, 2:43 PM
Jayakrishna 🇮🇳
+ 1
Jayakrishna🇮🇳 you mean you want to see the judge system ?
3rd Sep 2022, 2:52 PM
Ali_combination
Ali_combination - avatar
+ 1
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
3rd Sep 2022, 3:18 PM
Patrick
Patrick - avatar
+ 1
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.
3rd Sep 2022, 5:07 PM
Ali_combination
Ali_combination - avatar
+ 1
''' 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
4th Sep 2022, 5:45 AM
Bob_Li
Bob_Li - avatar