programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Binary search and not non decreasing input

Ranch Hand
Posts: 188
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

author and iconoclast
Sheriff
Posts: 24217
38
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
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

Sheriff
Posts: 11343

Originally posted by Andrew Mcmurray:
...Sound kinda right? ...

Exactly!

Andrew Mcmurray
Ranch Hand
Posts: 188
Cool thanks

 Don't touch me. And dont' touch this tiny ad: The WEB SERVICES and JAX-RS Course https://coderanch.com/t/690789/WEB-SERVICES-JAX-RS