Understanding Binary and Linear Search Algorithm C++

What is Binary Search?

Binary Search is also popularly known as logarithmic or half-interval search, that finds the element given to us in the sorted array. As the name suggests binary search binary means involving two things and search simply means to search the element, hence “binary search” searches for the element involving two arrays (each time we search for the element) or you can simply say by partitioning an array into two halves (each time we search for the element) based on the total number of elements present in the array.

Algorithm:

Unlike linear search, the algorithm for binary search is a bit tricky but easy to understand as the implementation of binary search is simple and general and below is the complete algorithm for binary search.

Step1: Declare a function with return type as binary-search with arguments as (arr [ ], int low, int high, int key).

Step2: Let (low) be a variable which stores the minimum index of the array and let (high) be the variable which stores the maximum index of the array and variable (key) with the array element to be searched.

Step3: Check whether (high >= low) if “Yes” then move to step 4 else moves to step 7.

Step4: Declare a variable mid and assign it with the average value of low and high or to avoid overflow condition, you may use mid = low + (high - low) / 2 rounded, so that it is an integer value.

Step5: Now check whether the key to be searched in the array is equal to the element at the mid-position of the array if “Yes” then return mid, else go to step 6.

Step6: In this step check whether the key to be searched is greater to the element at the mid-position then return to the function binary-sort with arguments (arr, mid+1, high, key) else return to the function binary-search with arguments (arr, low, mid-1, key).

Step7: This step determines that the key to be searched in the array is not present in the array and return with the value -1.

Now let us take an example of an array of size 7 with array elements as [1, 2, 3, 4, 5, 6, 7]. Now suppose we have to search for the number 5 in the given array, then according to the above algorithm.

We will find the mid-element of the array according to the algorithm given above by using the relation mid = low + (high - low) / 2, here our mid-element will be 4. Now next we since we have to search for the key number 5 in the array, so we compare the key number 5 with the mid-element of the array which is 4, now since 5 > 4, so we will ignore the Partition 1 of the array and move on to Partition 2 of the array, now we will further divide the Partition 2 array according to the algorithm above by using the relation mid = low + (high - low) / 2.

As shown in the image below is how we are further finding the mid-element in the other half of the array or our Partition 2 array.

Now since we see that the mid-index of the array holds the key number or the number which we were to find in the given array, hence we now return the index of the array where the key number is found which is our mid, and hence we have found the index of the key number 5 in the array with the help of binary search.

Note that binary search is only applicable in a sorted array whether it is increasing or decreasing.

Implementation Of The Above Algorithm:

Implementation of the above-given algorithm is as follows:-

#include <bits/stdc++.h>
using namespace std;
/*Function to perform the binary search. */
int binary_search(int arr[], int low, int high, int key)
{
	if (high >= low)
	{
		int mid = low + (high - low) / 2;
		/*Finds mid index of the array. */
		if (arr[mid] == key)
			return mid;
		else if (arr[mid] < key)
			return binary_search(arr, mid + 1, high, key);
		else
			return binary_search(arr, low, mid - 1, key);
	}

	/*Key not found. */
	return -1;
}

/*Driver function to check the above algorithm. */
int main()
{
	int arr[] = { 1, 2, 3, 4, 5, 6, 7 };

	int n = sizeof(arr) / sizeof(arr[0]);
	int x = 4;
	int t = binary_search(arr, 0, n, x);
	if (t == -1)
		cout << "Element not found" << endl;
	else
		cout << "Element found at index " << t << endl;
	return 0;
}

The time complexity of the above algorithm: O(logn).

The output of the above algorithm: Element found at index 3.

Time Complexity Analysis Of Binary Search:

Time complexity analysis of binary search can be done by carefully examining the steps taken to reach the key element to be found in the array, for example, if we consider an array of size 4 we will need at most 3 iterations to find the key element in the array, as first, we will divide the array into two parts each with 2 elements further we will divide the array into more two parts, and then we will search for the element is found then return the index else return -1 or exit as per our problem requirement.

We can easily calculate this by using the logarithmic relation as (log2x = 4)+ 1 steps here we have x = (2 + 1) = 3 steps and if we take the size of the array to be 8 then we will need at most 4 steps, so we can generalize our observation here that every time we double our array size we require at most one extra step to reach the key element.

For analyzing the time complexity of binary search we make use of the power of 2 as the name suggests binary, but even if the size of the array is not in the power of 2 we take the nearest power of 2 for that size of the array, for example, if the size of the array is 9 so the nearest power of 2 to 9 will be 8 which is 2^3 = 8, hence here we will require at most 4 steps to reach to our key element (we can try this for a bigger size of array the result in each case is according to the size of the array and the nearest power of 2) and hence the time complexity of the binary search is regarded as O(logn).

The worst case of binary search occurs when the element to be searched for is not present in the array and hence one needs to traverse the complete steps in the algorithm to reach the conclusion, and hence the time complexity of binary search at worst case is O(logn) with space complexity of O(1) as we need not declare another array to store the element to be found we are simply returning the index of the key element to the main function and simply printing its value.

The best case of binary search occurs when the key element to be found is at the mid-index of the array and searching gets over at a constant time in one iteration hence time complexity of binary search in the best case is O(1) i.e., constant time complexity.

Binary Search Vs Linear Search?

Binary Search is used to search for the element in the sorted array either increasing or decreasing, but you may ask why we require it when we have another search algorithm known as linear search, which we can use in both sorted and unsorted arrays, the answer to this question is simple as in linear search in the worst case its time complexity is O(n) but in case of binary search the time complexity in the worst case is just O(logn) which is much less than that of linear search time complexity (as you can take an example of n as 2 where log2 is simply 1.414 and n is 2 so 2 > 1.414 and hence logn < n you can also verify this for other numbers) also in case of linear search the time is taken in searching for the element in the array increases as the number of elements increases. The comparison of worst-case time complexities of binary and linear search can be shown below graphically:

However, for the best case both searches have the same time complexity of O(1) but we need not look up the best-case complexity of an algorithm as algorithms are judged upon their worst-case time complexity and space complexities of both the searches in O(1).