• Post Reply Bookmark Topic Watch Topic
  • New Topic

Binary search and not non decreasing input  RSS feed

 
Andrew Mcmurray
Ranch Hand
Posts: 188
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi all

I am writting a binary search method and I have heard that binary searches sometimes do not return the key if the search set is not in non decreasing order. Is this true? If it is why is this the case?

Thanks,

AMD
 
Ernest Friedman-Hill
author and iconoclast
Sheriff
Posts: 24217
38
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The whole binary search algorithm depends on the array being sorted; if it's not sorted, the algorithm doesn't work. If you know how the algorithm works, that should be pretty obvious, right?
 
Andrew Mcmurray
Ranch Hand
Posts: 188
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes I think I have it, but to be sure tell me if this sounds correct? First I compare the key to the middle of the array if it matches then it is it if not see if that value is bigger or smaller then the one we are looking for. If it is bigger then do the same as above, but only on the seond half of the array. Keep going to you either find it or run out of elements to check. So if I was looking for lets say 7 in an array of {1 2 3 4 5 6 7 8 9 10} it would first check 5 see it is not five and then cut the array in half so the second time it would only check {6 7 8 9 10} then {6 7}.

So if the array was in not non decreasing order like {1 2 7 3 4 5 6 8 9 10} and we were searching for 7, we would compare to 4(the middle) and then only check the upper half of the array (5 6 8 9 10} and never find it eventhough it is in the set.

Sound kinda right?

Thanks,

AMD
 
marc weber
Sheriff
Posts: 11343
Java Mac Safari
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Andrew Mcmurray:
...Sound kinda right? ...

Exactly!
 
Andrew Mcmurray
Ranch Hand
Posts: 188
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Cool thanks
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!