Printable View
Just curious, but suppose I have a set of numbers, 1 through 15, in numerical order. Is there an equation which can determine the number of searches it would take using a binary search to find a specific item? i.e., I know it takes 4 searches if I am searching for the number 1, but if I want 5? 14? Is there a better way of doing this than w/ pencil and paper?
Simple, find out what power of two yours is closest to, rather, the next closest higher if not an exact match, find what bit number that is, add one, that's how many searches it takes.
Example: 8 numbers = 3rd bit = 3 searches:
1-8
1-4 or 5-8
1-2 or 3-4 or 5-6 or 7-8
1 or 2 or 3 or 4 or 5 or 6 or 7 or 8
Quzah.
noOfSearches = ceiling(lgn) logarithm in base 2.
This gives you the maximum number of searches where n is the number of elements in the sequence. If the item is not in the sequence you make an extra operation too.
Quzah: I know this is simple for you, but me being a NB, it is not so simple, not right off the bat at least.
I followed you up to
But what does the following mean???Quote:
Example: 8 numbers = 3rd bit = 3 searches
Quote:
1-8
1-4 or 5-8
1-2 or 3-4 or 5-6 or 7-8
1 or 2 or 3 or 4 or 5 or 6 or 7 or 8
I can't believe y'all never played this game before...
I'm thinking of a number, from 1 - 64... what's the best way to guess it?
If you want to minimize your worst case # of guesses, then you just pick the middle number each time (that is, (1 + 64) / 2)...
32? Lower, so 1 - 31 -> 16
16? Higher, so 17 - 31 -> 24
24? Lower, so 17 - 24 -> 20
20? Higher, so 21 - 24 -> 22
22? Lower, so 21
21? Bingo!
See? I found it in 6 steps. Not bad, not compared to 21 most certainly.
Notice that there are cases where I had to round off. To find the worst case, I should have picked the range which gave me more values to eliminate.... for example, 1 - 31 isn't as many numbers as 33 - 64. We can do this by always rounding down and always having to pick the higher range, or by always rounding up, and having to always pick the lower range. Lower ranges are easier to deal with, so I'll try it rounding up...
33? Lower, so 1 - 32 -> 17
17? Lower, so 1 - 16 -> 9
9? Lower, so 1 - 8 -> 5
5? Lower, so 1 - 4 -> 3
3? Lower, so 1 - 2 -> 2
2? Lower, so 1
1? Bingo!
Aha, so the actually worst case, using a binary search is not 6 steps, as in the previous example, but 7.
So to find the worst case for say, 1 to 15, just use the same process. Always round up, and always have it turn out that the lower range is the correct one...
or always round down and have it turn out that the higher range is the correct one.
As it turns out, the time it takes to find a number this way is related to the base 2 logarithm of the range.