By examining the center value in an array that has already been sorted, Binary Search locates the target value. Linear Search chooses the left or right sub-array and keeps searching until the target value is found if the center value is not the desired value.

Let’s check how many compare operations are required to locate the target value in an array with Binary Search in order to determine the time complexity. n principles.

In an ideal world, the target value and the first middle value would match. In this case, the target value is immediately determined with a single comparison, meaning that the time complexity is O(1.) in this instance.

In the worst situation, the search area would have to be repeatedly divided in half until it consisted of just one value. When this occurs, whether or not the target value is found has no bearing on the time complexity.

Let’s look at array lengths that are multiples of two, such as 2, 4, 8, 16, 32, 64, and so forth.

Until we are left with just one value, how many times must we divide two? I mean, it’s just once, right?

What about eight? To get to only one value, we must divide an array of eight values in half three times.

It is necessary to reduce a 32-value array in half five times.

We can see that 2=21, 8=23 and 32=25. So the number of times we must cut an array to arrive at just one element can be found in the power with base 2. Another way to look at it is to ask “how many times must I multiply 2 with itself to arrive at this number?”. Mathematically we can use the base-2 logarithm, so that we can find out that an array of length ncan be split in half log2(n)times.

This indicates that Binary Search’s temporal complexity is

==formula===

Although the average case scenario is difficult to identify, it is not very interesting because, according to Big O notation, the time complexity of an algorithm is the upper bound of the worst case scenario.

Note: Binary Search Time Complexity is O(log2.n) significantly quicker than linear search O(n), but keep in mind that while Linear Search does not need a sorted array, Binary Search does.

This graph shows how long Binary Search takes, in comparison to Linear Search, to locate a value in an array of n values: