Let’s first understand what Searching is :
Searching means doing iterations over the data structure's elements to extract some data. To searching in an array data structure, there are two major techniques :
- Linear Search
- Binary Search
In this article, we will focus on Binary Search only.
So, firstly let’s see what is Binary Search?
Binary search is a searching algorithm that helps to find the position of the target element in a sorted array. In the world of computer science, Binary Search Algorithm is the ground of the “ Divide & Conquer” algorithmic paradigm. This algorithm is the simplest demonstration of how “Divide and Conquer” works.
You must already be familiar with Linear Search wherein an array of random numbers or can say unsorted numbers we can search a target value by matching it with every element of the array. But if we talk about Binary Search, it should be noted that working in Binary Search is totally different from what is followed by Linear Search. The most important condition of Binary Search is: It only works in an array with sorted elements.
Let’s now discuss its working:
Binary Search compares the target value to the middle element of the given array. If the element doesn’t match the target value, then according to the Binary Search algorithm, the sorted array is then divided into two parts. For that, we need to find the mid-index of the array.
The formula for finding the mid-index of the array is :
MidIndexOfArray = FloorValue[ StartIndexOfArray + EndingIndexOfArray ] / 2
The floor value is the nearest lower value of the answer to avoid the decimal convention. Example: In an array of sorted 10 elements, the mid index would be given by: Mid Index = Floor [ 0 + 9 ] / 2 = 4
Now, we have got the mid-index as 4.
Note: If the index counting of the elements starts from 0(also known as 0-based indexing), then it will go up to 9, so EndingIndexOfArray would be 9 in this case. If the index counting of the elements starts from 1(also known as 1-based indexing), then it will go up to 10, so EndingIndexOfArray would be 10 in this case.
We have currently considered 0-based indexing to calculate midIndexOfArray in the upper calculation.
The first part of the array will have elements that start from index 0 to mid means the first part will have elements from index 0 to 4 The second part of the array will have elements that start from the (mid+1)index to EndIndexOfArray means that the second part will have elements from index 5 to 9.
It would be more fun to understand this by a real-life example that how Binary Search makes our tasks simple in our real-life too :
Suppose there’s a college nearby a society and there are 100 houses in a society and have addresses starting from 500A to 600A. I with my friends have to look for a PG to reside in the society, it has already been mentioned outside society that a PG facility is provided in house number 563A.
Now how should we find out between so many houses, the target house?
So, Let’s see how binary search can help me and my friends find the right house between so many houses …….
All the houses from address 500A to 600A are treated as elements of an array. 0-based indexing has been used to mark the indexes of each of the houses. If we look closely at the elements the startingIndexOfArray will be 0 i.e the house address no 500A and endingIndexOfArray will be 100 i.e the house address no 600A. To find the mid house address, we used the formula of midIndexOfArray
midHouseAddress = FloorValue[startingHouseAddress + endingHouseAddress] / 2
midHouseAddress = FloorValue[0 + 100] / 2 = FloorValue[100] / 2
midHouseAddress = FloorValue[50] = 50
This means the house address at index no. 50 is the middle house i.e HouseAddress 550A
According to what we learned above, the house array will be divided into two parts : [ HouseAddress 500 A - HouseAddress 550A ] and [ HouseAddress 551A - HouseAddress 600A ]
Now, according to the targetted House Address i.e 563A, our target address is in the second half of the array. So, for our convenience, we will update the startHouseAddress as 551A and endingHouseAddress as 600A.
Again, let’s find the midHouseAddress by using indexes of houses :
midHouseAddress = FloorValue[51 + 100] / 2 = FloorValue[151] / 2
midHouseAddress = FloorValue[75.5] = 75
This means the house address at index no. 75 is the middle house now i.e HouseAddress 575A.
According to what we learned above, the house array will be divided again into two parts : [ HouseAddress 551 A - HouseAddress 575A ] and [ HouseAddress 575A - HouseAddress 600A ]
Now, according to the targetted House Address i.e 563A, our target address is in the first half of the array. So, for our convenience, we will update the startHouseAddress as 551A and endingHouseAddress as 575A.
Again, let’s find the midHouseAddress again by using indexes of houses:
midHouseAddress = FloorValue[51 + 75] / 2 = FloorValue[126] / 2
midHouseAddress = FloorValue[63] = 63
Hurray!!!! We got the targetHouseAddress.
Meanwhile me and my friends 🤠
So, we got the target house address at index number 63 which is HouseAddress 563A.
Case :
If let’s say the target house address of the PG would have been 613A. Then it’s clear that after doing the binary search too, we wouldn’t have found 613A at any index, but the partitioning of the array would have to be done continuously until it becomes empty. So, it simply meant that 613A is not present in this society or in the given house array.
Now, let’s have a look over the algorithm or basic code of Binary Search :
Let’s have a quick understanding of this : In binary search function, it takes 2 parameters, the array itself and the value or target value to search in the array. The start index will obviously be 0 and the end index will be the length of the array. Till the start index is smaller than or equal to the end, the while loop will execute all the mentioned instructions. After that mid-value was calculated according to the formula, we discussed above. The condition next is, that if the target value is equal to the array’s mid-value, then simply return the index
Else if the target value is smaller than the mid-index of the array, then it’s time to partition the array into two. So after that, the first half will have start = 0 and end = mid And the second half will have start = mid+1 and end = array.length-1 And we have to deal with the first half.
Else if the target value is larger than the mid-index of the array, then it’s time to partition the array into two. So after that, the first half will have start = 0 and end = mid And the second half will have start = mid+1 and end = array.length-1 And we have to deal with the second half.
Now let’s discuss the time and space complexity of Binary Search in various scenarios:
Best Case:
This means we found the target value in the first go.
Worst Case:
This means we didn’t found the target value after so many partitions till the array became empty.
Average Case:
This means we found the target value after so many partitions but before the array became empty.
Using this algorithm searching can be done in O(log(n)) time wherein linear search if you remember it takes O(n) time in the worst case. So Binary Search saves time and makes fewer comparisons to search the target value.
Note:
Although Binary Search is faster than the Linear Search but only for large length arrays. In the case of small length arrays, the linear search can be used to find the targeted value faster.