In today’s article about search algorithms, we will talk about binary search. Algo.monster will share detailed information about this search approach.
According to Wikipedia, you can also call this algorithm the half-interval search, logarithmic search, or binary chop. Whichever name you prefer, it is an efficient way of searching.
Well, let’s take a look at this popular search technique in detail.
What is a binary search algorithm about?
Before we come to the formal definition, let’s play a guessing game.
So, now I’m writing down a letter from the alphabetic table which is from A to Z. Suppose the letter I write down is O.
Now, it’s your job to guess within minimum times about which letter I’ve written down. Well, do you know which is the fastest way to do it?
Then, let’s come to the introduction of binary search.
Binary search
It is a searching algorithm that helps to find the element within the array and return its index. A flag value could be returned to indicate that an element does not exist.
Binary Search employs the divide-and-conquer policy. This means that each comparison is made by repeatedly dividing an array into two parts.
You cannot apply it to monotonic functions or sorted arrays.
What are the steps binary search functions?
The first step in our search is to define two pointers: low and high.
So, low points will be indexed 0 and high points will be indexed arr.length-1. The array should be sorted in ascending orders. Then, we will find the middle item and compare it with our target element. Normally, there will be three possible scenarios.
When the data is arranged in increasing order:
If the middle element equals the target item, then our search ends.
However, if the middle element tends to be higher than the target value, then, we keep on searching toward the left side. The left side is the lower part.
Then, if the middle value is less than the target element, we move towards the right side.
To make it easier to understand, let’s look at this example below
Let’s suppose that element 50 is missing from our given array.
Our low pointer = 0 and high pointer = 6.
Then, we define a loop in which we work low to high.
So, we find the mid-value is (low+high)/2.
However, if the array length is O(10^9) or more, then the above formula could cause an overflow error. Therefore, we need to use mid = low + (highly-low)/2. Actually, this would provide the same answer as above but avoid an overflow error.
First, we find mid = (0+6)/2= 3 => mid value = 45. Since 45 < 50 => changing the low, continue towards right with middle+1.
Then, again, find the new mid = (4+6)/2= 5 => middle value = 71. Because 71 > 50 => we shift towards the left by changing the high = middle-1
Next, we find mid = (4+5)/2= 4 => the mid value = 50. Obvious, 50 is our target=> which means we find mid = (4+5)/2 = 4 => Mid value = 50.
Finally, if we are unable to find the target value within the list, we will return false (or any flag values) or -1.
Thus, we know this particular type of search algorithm splits the array into halves in each iteration.
Time and space complexity
Complexity of Time
Best time complexity: O(1). This is because the element is present at a middle index. One comparison is needed.
Average time complexity: This is the average complexity of finding the element at each index. This is because the array is split in half every iteration:
1-1/2-1/4-1/8…or n-n/2-n/4…n/(2^k)
Here is an example of a recurrence relation: T(n) = T/2) + c (constant c).
This relation can be solved with a Master Method or Recurrence Tree, which would give a complexity of O(log n (base 2).
Worst time complexity: O(log n (base 2)).
Space Complexity: O(1).
We don’t create or use any space beyond the array length we have given as input. N is the total number of elements in the array
Binary Search’s Advantages
It is easy to understand both concepts and how they are implemented.
While it does require a sorted array to be effective, it’s extremely useful for efficiently searching an element in a long list because it breaks down each collection in half.
The searching begins in O(1) when the target element matches that of the array’s middle element.
Linear Search VS. Binary Search
| Linear Search | Binary search |
| Iterative or sequential approaches are used | Binary follows a divide and conquer strategy |
| It does not depend upon the arrangement of elements within an array | This method needs to be arranged in increasing or decreasing order |
| O(N) is the worst-case complexity of linear search | Worst-case complexity of binary Search is O (log 2 N) |
| Linear sequentially accesses all elements | It accesses data randomly |
| Perform equality comparisons | Binary performs ordering comparisons |
| Best case is when an element can be found in the 1st position. | The Best Case is when an element can be found in the middle position. |
| Less complicated | More complex |
| Inefficient | More efficient |
Which is faster: binary or linear search?
Binary search is quicker than linear search. Also, binary search’s worst-case complexity is O(log2 N), while linear search’s is O(N). Binary search cannot be applied to an array that is not sorted. Linear search does not require such conditions.
Finally, let’s continue with the guessing game from the beginning
So, how can you guess it right using the possible least steps?
First, let’s try linear search.
It’s obvious that, if we start from A, we have to go through 14 steps before we reach O.
On the other hand, if we use binary search. Things are quite different. You can try the process yourself.
Conclusion
From what we’ve mentioned above, it’s easy to come to this conclusion: binary search is an efficient approach to finding an item. Just you have to keep one thing in mind: it only works for sorted data.
Next time, if you need to find a book from the library bookshelf, which method will you use to search for it: linear or binary search?
