Is it possible to do a binary search on an unordered list, and if so, what would the code look like? Thank you very much for the help.
3
-
1Does this answer your question? Binary search in a Python listVivs– Vivs2022-11-15 14:43:01 +00:00Commented Nov 15, 2022 at 14:43
-
1No, you can't. The basic logic of binary search requires a sorted list.John Coleman– John Coleman2022-11-15 14:44:00 +00:00Commented Nov 15, 2022 at 14:44
-
1No dear. It is not possible. It has be sorted. Otherwise, the logic will fail to search the element as binary search checks the mid values and then proceed ahead in either of direction assuming it is sorted.Nish– Nish2022-11-15 14:44:48 +00:00Commented Nov 15, 2022 at 14:44
Add a comment
|
1 Answer
Read this Binary Search.
In the second line it says
"...is a search algorithm that finds the position of a target value within a sorted array."
If we have the following list: lst = [1, 3, 4, 6, 2, 9, 8, 5, 7], and we want to find where 6 is.
We would look at the element in the middle of the list. In this case 2, the algorithm checks to see if 2 < 6 and that is in fact true. The algorithm would now search for 6 in the right sub-list, i.e. [9, 8, 5, 7] because it assumes a sorted list and it will not be able to find our target 6.
So in short, you can not do binary search on an unordered list.
