Please refer here to the direct resource that I don't understand.
Let's take the number X = 245436, we can represent the following as X = 2 * 10^5 + 4 * 10^4 + 5 * 10^3 + 4 * 10^2 + 3 * 10^1 + 6 * 10^0 using decimal expansion. So, the minimum amount of information we need to represent this number is 6 digits. This is no coincidence, as any number less than 10^d can be represented in d digits.
So how many digits are required to represent X? Thats equal to the largest exponent of 10 in X plus 1.
==> 10^d > X
==> log(10^d) > log(X)
==> d* log(10) > log(X)
==> d > log(X) …and log appears again...
==> d = floor(log(x)) + 1
I can follow through his illustration and example, but it's the next example that confuses me. when he tries to relate searching for a number in a range from 0 -> N -1.
Here's his explanation:
Taking N = 10^d, we use our most important observation:
The minimum amount of information to uniquely identify a value in a range between 0 to N - 1 = log(N) digits.
This implies that, when asked to search for a number on the integer line, ranging from 0 to N - 1, we need at least log(N) tries to find it. Why? Any search algorithm will need to choose one digit after another in its search for the number.
The minimum number of digits it needs to choose is log(N). Hence the minimum number of operations taken to search for a number in a space of size N is log(N).
What I don't understand
This implies that, when asked to search for a number on the integer line, ranging from 0 to N - 1, we need at least log(N) tries to find it. Why? Any search algorithm will need to choose one digit after another in its search for the number.
Specifically
Why? Any search algorithm will need to choose one digit after another in its search for the number.
Can someone show me an illustration of this?
If we had 10 elements in an array (n = 10)
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9
And I'm trying to find the what index gives me the value 5? That means I need log(10) tries to find it? Firstly log of base 10? That's log 10 = 1. I don't see how that makes sense? If I use base 2 I get = 3.
It means I'm taking a minimum of 3 operations to find x? Why? Can someone illustrate it?
I just don't see how the decimal expansion relates to finding a value in a range 0 - n.
As an answer to your question: "Why? Any search algorithm will need to choose one digit after another in its search for the number"
The search algorithm that's O(log(n)) relies on the data being sorted, such that if it checks an element and that element's greater than the requested one, it can discard everything after that because all of those must also be greater.
In computer science log is typically considered to be log base 2 unless stated otherwise, I make it unique by calling it lg(n).
For your particular example, say you're searching for "2" A O(log(n)) algorithm will work similar to as follows. 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9
Check the middle element, 4. Is 4 greater than 2? Yes. Therefore, disregard everything after 4 and check the middle between 0 and 4. 2 is the middle, we found that number in 2 steps. In the worst case it takes floor(lg(n)) + 1 steps, because each time you're dividing the number of unchecked elements by 2, the + 1 comes from edge cases. Also, floor(lg(n)) + 1 references the worst case scenario, not the best case scenario. In the best case, this particular algorithm could get the answer in 1 step.