Question

If you have a SORTED array of numbers, is is possible to find the largest number that is less than a VALUE in O(logN) time? There is no guarantee that the key is actually in there. For example, "What is the largest key smaller than 10000 in a sorted array". I believe it is O(N) to find it, because we would have to search all the keys, and binary search would be useless if there is no guarantee a key is actually in there If you have a SORTED array of numbers, is is possible to find the largest number that is less than a VALUE in O(logN) time? There is no guarantee that the key is actually in there. For example, "What is the largest key smaller than 10000 in a sorted array". I believe it is O(N) to find it, because we would have to search all the keys, and binary search would be useless if there is no guarantee a key is actually in there @Computer Science

Answer 1

why do you say binary search is useless?

Answer 2

Well, say we have these values in our array 1,2,3,4,6,7,8,9 . If we look for 5, binary search will not be helpful, since it is not in there. So I then I applied this to my problem. It would be very easy to do a binary search for 10000, then just look at the element that is smaller than it. But if 10000 is not in the array, we won't be able to do this. Is my logic right?

Answer 3

your logic is not correct. it makes no difference whether the value is in the set of numbers being searched or not.
the algorithm would go something like this:
1. look at the middle element - in your example this woud give us 4
2. we check if this is less than the value: 4 < 5? answer is yes, keep this value and search in the top half
3. we look at the value in the middle of the top half - 7 in your case
4. 7 < 5? answer is no, so we search in the lower half
5. this is just 6, do the check 6 < 5? answer no so we are left with 4 as the answer

Answer 4

so you do not need to search EVERY element in the list with binary search

Answer 5

So, what you are saying is that we should run a binary search for 10000, and if 10000 is found, just go one element over. If it is not found, then we should use the element that binary search has "trapped", and look at elements on both sides to determine which is the correct one?

Answer 6

that is correct - you have got the idea now

Answer 7

except you don't look on both sides, but rather continue the binary search

Answer 8

so if element you land on is less than the value you are looking, store it and do a binary search on the remaining upper half, else ignore it and do a binary search in the remaining lower half

Answer 9

I see what it is now. We have the knowledge that the list is sorted, so we should use that to our advantage. It makes sense conceptually. Thanks!

Answer 10

good - I'm glad you "grokked" it in the end :-)

Answer 11

we all use binary search algorithms without knowing it, when we look up for numbers in the phone book. we always seem to flip to the middle of the book first