About Binary Search
Binary search works on a sorted collection of elements, such as an array.
The basic idea behind binary search is to repeatedly divide the search interval in half.
It has a time complexity of O(log n) where "n" is the number of elements in the array. This makes it much more efficient than linear search for large data sets.
How do we implement binary search?
Here's the algorithm behind it:
Binary search works by repeatedly dividing the search range in half until the desired element is found or the search range becomes empty.
Start with a sorted array: Binary search requires that the input array is sorted in ascending order.
Initialize variables:
start- The index of the leftmost element in the search range (initially 0).end- The index of the rightmost element in the search range (initially the length of the array minus 1).
Repeat until the search range is empty: a. Calculate the middle index as
mid = (start + end) / 2. b. Compare the element at the middle index with the target element. c. If the middle element is equal to the target, return its index (search successful). d. If the middle element is less than the target, updatestarttomid + 1. e. If the middle element is greater than the target, updateendtomid - 1.If the loop exits without finding the target, return -1 to indicate that the element is not in the array.
Code using binary search algorithm
class HelloWorld {
public static void main(String[] args) {
int[] arr={23,34,45,56,67,78,98,100};
int data=98;
System.out.print(binarySearch(arr,data));
}
static int binarySearch(int[] arr, int data){
int s=0;
int e=arr.length-1;
while(s<=e){
int mid=s+(e-s)/2;
if(data<arr[mid]){
e=mid-1;
}else if(data>arr[mid]){
s=mid+1;
}
else{
return mid;
}
}
return -1;
}
}
Oder-Agnostic binary search
Order-agnostic binary search is a smart way to know, whether the list is arranged from smallest to largest(Ascending) or largest to smallest(Descending).
class HelloWorld {
public static void main(String[] args) {
int[] arr={100,98,76,65,54,43,23};
int data=98;
System.out.print(OrderAgnostic(arr,data));
}
static int OrderAgnostic(int[] arr, int data){
int s=0;
int e=arr.length-1;
boolean isAsc=arr[l]<arr[r];
while(s<=e){
int mid=s+(e-s)/2;
if(data==arr[mid]){
return mid;
}
if(isAsc){
if(data<arr[mid]){
e=mid-1;
}else{
s=mid+1;
}
}
else{
if(data>arr[mid]){
e=mid-1;
}else{
s=mid+1;
}
}
}
return -1;
}
}
Note
Binary search is highly efficient and suitable for large sorted data sets.
It is commonly used in situations where you need to quickly find an element in a sorted list, such as searching in a sorted array or a dictionary.
Performance
Binary search has a time complexity of O(log n), making it very efficient for large data sets.
It divides the search space in half with each iteration, leading to fast search times.
For you to understand how efficient it is, let's take an example array of 1 million elements. In the worst-case scenario in a linear search algorithm, 1 million comparisons are made. However, in binary search algorithms, only 20 comparisons are made. I hope now you can understand the difference.
Conclusion
Binary search is a powerful and efficient algorithm for searching in sorted data sets. Binary search is widely used in computer science and is a fundamental algorithm for tasks involving searching and retrieval in sorted datasets. It is a key concept in algorithm design and is often used as a building block for more complex algorithms.. When you need to find elements in a sorted list, binary search is a go to choice. Stay tuned to know more about binary search, we will be solving programs related to binary search in our next chapter. Until then cheers to all, happy coding!!