| |
Worst case Binary Search number of
inspections
Well, the big question is "What is the most number of times I can cut my
file in half?" Let's say we have N records in a file. The first time we
cut it in half, we have N/2 records left. The next time we would have (N/2)/2
or N/4 or N/22. The next time we'd have ((N/2)/2)/2 or N/8 or
N/23
OK, so we can see a pattern. It looks like the most number of times we can cut
it in half is N/2x, but what is x?
Let's assume when we have finished cutting the file in half for the last time
we'll have 1 record left. That would look like this: |
|
| |
| If we start with
100: |
If we start with
1,000: |
50
25
12
6
3
2
1
----
7 times |
500
250
125
62
31
16
8
4
2
1
----
10 times |
|
|
| |
OK, so if we can say we'll have 1 record left,
after dividing N in half x times, we can write N/2x=1. Now we have a
formula we can solve for x: N/2x=1
N=2x
Log N=Log 2x
Log N=x Log 2
Log N/Log 2=x
Plugging in both 100 and 1,000 for N matches the
expected values above (7 and 10 respectively). Well, that's what my thought
process was anyway. If anyone can add to or
refine this, I'll add it to this page, with due credit.
Return to
Development Tools
|
|
|
