Here is wikipedia entry

If you look at the simple iterative approach. You are just eliminating half of the elements to be searched for until you find the element you need.

Here is the explanation of how we come up with the formula.

Say initially you have N number of elements and then what you do is
⌊N/2⌋ as a first attempt. Where N is sum of lower bound and upper bound. The first time value of N would be equal to (L + H), where L is the first index (0) and H is the last index of the list you are searching for. If you are lucky, the element you try to find will be in the middle [eg. You are searching for 18 in the list {16, 17, 18, 19, 20} then you calculate ⌊(0+4)/2⌋ = 2 where 0 is lower bound (L - index of the first element of the array) and 4 is the higher bound (H - index of the last element of the array). In the above case L = 0 and H = 4. Now 2 is the index of the element 18 that you are searching found. Bingo! You found it.

If the case was a different array{15,16,17,18,19} but you were still searching for 18 then you would not be lucky and you would be doing first N/2 (which is ⌊(0+4)/2⌋ = 2 and then realize element 17 at the index 2 is not the number you are looking for. Now you know that you don’t have to look for at least half of the array in your next attempt to search iterative manner. Your effort of searching is halved. So basically, you do not search half the list of elements that you searched previously, every time you try to find the element that you were not able to find in your previous attempt.

So the worst case would be

[N]/2 + [(N/2)]/2 + [((N/2)/2)]/2.....

i.e:

N/2^{1} + N/2^{2} + N/2^{3} +..... + N/2^{x} …..

until …you have finished searching, where in the element you are trying to find is at the ends of the list.

That shows the worst case is when you reach N/2^{x} where x is such that 2^{x} = N

In other cases N/2^{x} where x is such that 2^{x} < N
Minimum value of x can be 1, which is the best case.

Now since mathematically worst case is when the value of

2^{x} = N

=> log_{2}(2^{x}) = log_{2}(N)

=> x * log_{2}(2) = log_{2}(N)

=> x * 1 = log_{2}(N)

=> More formally ⌊log_{2}(N)+1⌋

1

this might help you: http://stackoverflow.com/a/13093274/550393

– 2cupsOfTech – 2016-05-20T04:00:32.043