Logarithmic Log_{2}N functions needs amount of time that is in logarthimc propotional to the number of input elements.

Assume that you want to search the number from sorted set of elements. You have sorted set {3, 5, 8, 9, 41}.

Start with the middle element and do comparison. If you find the number in first attempt, that is best case. But here middle element is 8. That is not the number you are searching (number 41). Since you know that this is sorted set of elements and hence you just need to check from the middle element to last element. You can simply ignore the other half of the set. Again apply similar logic to the upper half of the set. Continue till you find the elements or reach to a conclusion that number does not exist.

As you can see that in each attempt, number of elements is reduced by half. So in a set of 1000 numbers, the worst case scenario will be like this :

1. After 1st attemept, you are left with 500 numbers.

2. After 2nd attemept, you are left with 250 numbers.

3. After 3rd attemept, you are left with 125 numbers.

4. After 4th attemept, you are left with 62 numbers.

5. After 5th attemept, you are left with 31 numbers.

6. After 6th attemept, you are left with 15 number.

7. After 7th attemept, you are left with 7 numbers.

8. After 8th attemept, you are left with 3 number.

9. After 9th attemept, you are left with 1 numbers.

10. After 10th attemept, you know the result. Either you found the matching number or you know for sure that number does not exist in the given set of numbers.

As you can see that worst case scenario needs only 10 comparison.

In mathematical terms if the number of elements is N, it will check log_{2}N numbers. Hence it is called logarithmic function.

Binary Search Tree has log_{2}N time complexity for searching an element from the tree.

Java is a trademark of Oracle.

Apekshit.com is just for learning and testing. To improve basic understanding we provide some examples. We are constantly reviewing it to avoid errors, but we cannot warrant full correctness of all content.