I saw some videos about O(log n) time complexity, but then I tried a couple of binary search method on the Internet tutorial, and I am more confused now.

In computer science, big O notation is used to classify algorithms according to how their running time or space requirements grow as the input size grows.

An example binary search: https://jsfiddle.net/Hoyly/mhynk7gp/3/

function binarySearch(sortedArray, key){
    let start = 0;
    let end = sortedArray.length - 1;

    while (start <= end) {
        let middle = Math.floor((start   end) / 2);
                console.log('count',  count,sortedArray[middle]);
        if (sortedArray[middle] === key) {
            return middle;
        } else if (sortedArray[middle] < key) {
            start = middle   1;
        } else {
            end = middle - 1;
        }
    }
    return -1;
}
let count= 0;
console.log('first 1:');
let res1 = binarySearch([1,2,3,4,5,6,7,8],8);
console.log('first 2:');
let res2 = binarySearch([1,2,3,4,5,6,7,8],1);
console.log('answer:',res1,res2);

As you can see in the jsfiddle

If I try to find "1" in 8-length array

1. The method calling count is 3
2. 2^3 = 8
3. It is how people call it is a O(log n) function

But If I try to find "8"

1. The calling count is 4
2. 2^4 != 8
3. It is definitely not O(log n) definition from the worst case

CodePudding user response：

The time complexity is O(log n), not log n without the big O. I won't explain the full meaning of big-O here; see the definition on Wikipedia for that.

Suffice to say that it only gives an upper bound on the growth rate of the runtime as n grows, and only when n is big enough. Even if n = 8 resulted in 1000 calls, the algorithm could still be O(log n).

CodePudding user response：

The binary search here can do one extra step depending on which half of the array you are searching in. If it used Math.ceil instead of Math.floor then 8 would be found in three steps, while 1 would be found in four.

If we expand this to 128 items, then the last item would be found in 7 or 8 steps (again, depending on which half). In general, the real worst case for the steps taken would be log n 1. However, for big O, we do not consider the constants, only the growth rate of the function. O(log n 1) simplifies to O(log n). The same way how O(2n) is still O(n).