Why not linear search?
When it comes to search algorithms, Linear search is the simplest option available. Linear search goes through every element in an array, starting from the first, until it finds the target element. However, simplicity comes at a cost, and Linear search often falls short in terms of efficiency. This is because in the worst-case scenario, where the target element is at the last index, say n, of the array, the algorithm may have to check n times, making this process very slow.
However, there is a solution to this problem - Binary Search.
What is binary search?
Binary search is a searching algorithm used for sorted arrays.
In this, we take the middlemost element of the array
⁍ if target > middle —→ search in the right side
⁍ if target < middle —→ search in the left side
⁍ if target = middle —→ we have found our answer
now we search the new array that has formed on the right/left side take the middle element again, and go through all the steps again till we arrive at the target element.
Comparing Efficiencies
To demonstrate the efficiency of Binary Search, let's take an example of a large array of size 10^9. Linear search would take about 500 million steps to find the target element, whereas Binary search would take only 30 steps. That's a huge difference in efficiency!
Big O Notations
In terms of Big O notation, Linear search has a time complexity of O(n), whereas Binary search has a time complexity of O(log n). The logarithmic time complexity of Binary search is much more efficient than the linear time complexity of Linear search.
The code
Here is a Java code for a simple binary search.
public class binarysearch {
public static void main(String[] args) {
int[] arr = {2, 4, 7, 9, 12, 23, 45, 56, 67, 78};
int target = 45;
int ans = binarysearch(arr, target);
System.out.println(ans);
}
//return index
static int binarysearch(int[] arr, int target){
//initializing start and end points
int start = 0;
int end = arr.length - 1;
//loop starts
while(start<=end){
int mid = start + ((end - start)/2); //same as (start + end)/2
if(target< arr[mid]){
end = mid-1;
}
else if(target>arr[mid]){
start = mid + 1;
}
else{
return mid;
}
}
return -1;
}
}
This code will output the index of the target if found in the array. In this case, the target element which is 45 lies on the 6th index. Hence, the code will print 6.
Limitations
One limitation of Binary search is that it only works for sorted arrays. If the array is not sorted, we need to sort it first before we can apply Binary search. Another limitation is that Binary search only works for unique elements. If there are duplicate elements in the array, Binary search may not return the correct index.