binary search strings
Hi, ive tried looking this up for confirmation, ive seen pages saying it works for sorted, but looking for confirmation that it only works for sorted strings. I am wondering if binary searches, only works for strings that have been sorted into an order. And does not work for strings in a random order?
How could a binary search work with unordered data?
Do you even know what a binary search is?
Do you even know what a binary search is?
yes thats why im double checking, cause ive been told to use it on a data structure that cant be sorted, so thats why i was wondering.
well edit actually, im not completely familiar with the binary search, ive only recently been introduced, thats why I am double checking
well edit actually, im not completely familiar with the binary search, ive only recently been introduced, thats why I am double checking
Last edited on
Yes in order to do a binary search the container must be sorted.
What kind of data structure are you trying to use?
Why can't it be sorted?
| cause ive been told to use it on a data structure that cant be sorted, |
What kind of data structure are you trying to use?
Why can't it be sorted?
It's just such a stupid question.
How could a binary search work on an unsorted array?
It's not magic.
It's a very simple procedure, and it obviously requires a sorted array.
How could a binary search work on an unsorted array?
It's not magic.
It's a very simple procedure, and it obviously requires a sorted array.
binary search determines which half of a data structure holds your value. It does that because it is sorted, if you have 1,2,3,4,5,6,7 and you asked for 6, the middle value is 4. 6 > 4. 6 must be in the back half. It then searches 4,5,6,7 and so on, throwing away half each time until it finds it or shows it is not there at all.
now consider 1,7,6,2,3,4,5 ... looking for 6 again. Which half is it in? The computer sees 1,2,and 5 to make this choice, it does not see the whole array. What criteria do you have that tells you 6 is in the front half? Nothing.
There are other ways to search or sort data, if you cannot sort it as is. You can make a copy (simple data) or a light copy (heavy data, eg objects take a vector of pointers to them, sort the pointers by the data) if nothing else.
now consider 1,7,6,2,3,4,5 ... looking for 6 again. Which half is it in? The computer sees 1,2,and 5 to make this choice, it does not see the whole array. What criteria do you have that tells you 6 is in the front half? Nothing.
There are other ways to search or sort data, if you cannot sort it as is. You can make a copy (simple data) or a light copy (heavy data, eg objects take a vector of pointers to them, sort the pointers by the data) if nothing else.
Topic archived. No new replies allowed.