Binary Search in Data Structure
There are various ways to search a particular element from a given list. One of them is Binary search.
When there exists so much data everywhere, it is very necessary to have a good searching method to search for the particular data in lesser time.
Binary search works faster than linear search. It is one of the fastest searching algorithms.
What is Binary Search?
It is a searching technique. It is based upon Divide and conquer strategy. Binary search is applicable only on sorted data. It takes O(log n) time for completion.
It divides the given array into halves and then checks the middle element. If the middle element is smaller than the element to be searched, the algorithm selects the second half of the array and discards the first half.
Thus, at every step, the binary search algorithm keeps on discarding half of the array based on the value of the middle element. This process continues until the array becomes of the size 1 or 2 and the algorithm finally gets the required element.
If the search is successful i.e. the element is present in the array, it returns the index of that element. If the element is not present inside the array, the algorithm returns -1.
Working of Binary Search
Let us understand the working of a binary search algorithm with the help of an example.
Consider a sorted array having 10 elements as shown:
Suppose we wish to search 38 in the array.
Step 1: Find the middle element of the array.
index(Middle) = index(low) + index(high – low)/2.
Here, middle = 0 + (9-0)/2 = 4 i.e. the element at the 4th index i.e. 25.
Step 2: Compare 38 with the middle element. 38 > 25 So, discard the first half.
Step 3: Select the send half of the array. For the second half, low = middle+1 as shown:
Step 4: Find the middle element of this smaller array which comes out to 32. Compare 38 with 32.
38 > 32 Thus, discard the first half of this array.
Step 5: Select the remaining half of the array by doing low = middle+1 as shown:
Finally, we have found 38 and thus the algorithm will halt here.
Output: 8.
Pseudo-code for Binary Search
We can implement binary search in two ways:
1. Iterative approach
2. Recursive approach (Using divide and conquer)
The pseudo-code for binary search is given as follows:
Procedure Binary_Search(int Arr[], n) //Arr is an array of length n
key := value to be searched
Set low = 1
Set high = n
while x not found
if high < low
Display x does not exist
EXIT.
set middle = low + (high - low) / 2
if Arr[mid] < key
set low = middle + 1
if Arr[middle] > key
set high = middle - 1
if Arr[middle] = key
Display x found at location middle
EXIT.
end while
end procedure
Binary Search Algorithm:
1. Using Iterative approach:
Step 1: Set low = first_index, high = last_index, location = -1
Step 2: Repeat steps 3 and 4 while low <= high
Step 3: set middle = (low + high)/2
Step 4:
if Arr[middle] == key
set loc = middle
Display “The element to be searched is present at location: “ + loc
go to step 6
else if Arr[mid] < key
set low = middle + 1
else
set high = middle - 1
[end if]
[end loop]
Step 5:
if loc == -1
print "Element to be searched is not present in the array"
[end of if]
Step 6: Stop
2. Using Recursive approach:
int Binary_Search(Arr[], key, low, high)
middle = (low + high) / 2
if key == Arr[middle]
return mid
else if key > Arr[middle]
return Binary_Search(Arr[], key, middle+1, high)
else
return Binary_Search(Arr[], key, low, middle-1)
Implementation of Linear Search in C:
Iterative code:
int Binary_Search(int Arr[], int low, int high, int key)
{
while (low <= high) {
int middle = low + (high - low) / 2;
if (Arr[middle] == key)
return middle;
if (Arr[middle] < key)
low = middle + 1;
else
high = middle - 1;
}
return -1;
}
int main(void)
{
int arr[] = {2, 4, 8, 17, 25, 27, 32, 38, 45};
int len = sizeof(arr) / sizeof(arr[0]);
int key = 38;
int result = Binary_Search(arr, 0, len-1, key);
if(result == -1)
printf("Element not found");
else
printf("Element found at index: %d",result+1);
return 0;
}
Recursive code:
#include <stdio.h>
int Binary_Search(int Arr[], int low, int high, int key)
{
if (high >= low) {
int middle = low + (high - low) / 2;
if (Arr[middle] == key)
return middle;
if (Arr[middle] > key)
return Binary_Search(Arr, low, middle-1, key);
return binarySearch(Arr, middle+1, high, key);
}
return -1;
}
int main(void)
{
int arr[] = {2, 4, 8, 17, 25, 27, 32, 38, 45};
int len = sizeof(arr) / sizeof(arr[0]);
int key = 38;
int result = Binary_Search(arr, 0, len-1, key);
if(result == -1)
printf("Element not found in the array");
else
printf("Element is found at location: %d ",result+1);
return 0;
}
Binary Search implementation in C++
Iterative code:
#include <bits/stdc++.h>
using namespace std;
int Binary_Search(int Arr[], int low, int high, int key)
{
while (low <= high) {
int middle = low + (high - low) / 2;
if (Arr[middle] == key)
return middle;
if (Arr[middle] < key)
low = middle + 1;
else
high = middle - 1;
}
return -1;
}
int main(void)
{
int arr[] = {2, 4, 8, 17, 25, 27, 32, 38, 45};
int len = sizeof(arr) / sizeof(arr[0]);
int key = 38;
int result = Binary_Search(arr, 0, len - 1, key);
if(result == -1)
cout << "Element not found" ;
else
cout << "Element found at index " << result+1;
return 0;
}
Recursive code:
#include <bits/stdc++.h>
using namespace std;
int Binary_Search(int Arr[], int low, int high, int key)
{
if (high >= low) {
int middle = low + (high - low) / 2;
if (Arr[middle] == key)
return middle;
if (Arr[middle] > key)
return Binary_Search(Arr, low, middle-1, key);
return Binary_Search(Arr, middle+1, high, key);
}
return -1;
}
int main(void)
{
int arr[] = {2, 4, 8, 17, 25, 27, 32, 38, 45};
int key = 38;
int len = sizeof(arr) / sizeof(arr[0]);
int result = Binary_Search(arr, 0, len - 1, key);
if(result == -1)
cout << "Element not found in the array" ;
else
cout << "Element found at location: " << result+1;
return 0;
}
Implementation of Binary Search in Java:
Iterative code:
public class BinarySearch {
int Binary_Search(int Arr[], int key)
{
int low = 0, high = Arr.length - 1;
while (low <= high) {
int middle = low + (high - low) / 2;
if (Arr[middle] == key)
return middle;
if (Arr[middle] < key)
low = middle + 1;
else
high = middle - 1;
}
return -1;
}
public static void main(String args[])
{
BinarySearch obj = new BinarySearch();
int Arr[] = {2, 4, 8, 17, 25, 27, 32, 38, 45};
int key = 38;
int result = obj.Binary_Search(Arr, key);
if (result == -1)
System.out.println("Element not found");
else
System.out.println("Element found at index: " + (result+1));
}
}
Recursive code:
public class BinarySearch {
int Binary_Search(int Arr[], int low, int high, int key)
{
if (high >= low) {
int middle = low + (high - low) / 2;
if (Arr[middle] == key)
return middle;
if (Arr[middle] > key)
return Binary_Search(Arr, low, middle-1, key);
return Binary_Search(Arr, middle+1, high, key);
}
return -1;
}
public static void main(String args[])
{
BinarySearch obj = new BinarySearch();
int Arr[] = {2, 4, 8, 17, 25, 27, 32, 38, 45};
int len = Arr.length;
int key = 38;
int result = ob.Binary_Search(Arr, 0, len-1, key);
if (result == -1)
System.out.println("Element not found");
else
System.out.println("Element found at index: " + result+1);
}
}
Binary Search implementation in Python:
Iterative code:
def Binary_Search(Arr, low, high, key):
while low <= high:
middle = low + (high - low)//2
if Arr[middle] == key:
return middle
elif Arr[middle] < key:
low = middle + 1
else:
high = middle - 1
return -1
list = [2, 4, 8, 17, 25, 27, 32, 38, 45]
key = 38
result = Binary_Search(list, 0, len(list)-1, key)
if result == -1:
print ("Element not found")
else:
print ("Element found at location: % d" % (result+1))
Recursive code:
def Binary_Search (Arr, low,high, key):
if high >= low:
middle = low + (high - low) // 2
if Arr[middle] == key:
return key
elif arr[middle] > key:
return Binary_Search(Arr, low, middle-1, key)
else:
return Binary_Search(Arr, middle + 1, high, key)
else:
return -1
list = [2, 4, 8, 17, 25, 27, 32, 38, 45]
key = 38
result = Binary_Search(list, 0, len(list)-1, key)
if result != -1:
print ("Element foubd at location % d" % (result+1))
else:
print ("Element not found")
Complexity of Binary Search
Binary Search Time complexity:
| Case | Complexity |
| Best case | O(1) |
| Average case | O(log n) |
| Worst case | O(log n) |
Binary Search Space complexity:
In the worst case, the space complexity is O(1).
Linear Search v/s Binary Search
| Linear search | Binary search |
| It follows a sequential approach. | This follows a divide and conquer approach. |
| It works well on unsorted data. | To apply binary search, data has to be sorted. |
| Its worst-case time complexity is O(n). | Its worst-case time complexity is O(log n) |
| It is slower in comparison to binary search. | It is more efficient than linear search. |
| In linear search, we compare an element with every other element. | In binary search, we don’t compare an element with all other elements. We leave a few comparisons. |
| We prefer linear search only for small-sized data. | It is preferred for large-sized data. |
| We can implement linear search on all linear data structures like arrays and linked lists. | We can implement binary search only on those data structures that permit 2-way traversal. |
Applications of Binary Search
1. It is internally used in the inbuilt libraries of programming languages such as C, C++ and Java.
2. It helps to pinpoint the position of error during debugging of a particular code.
Conclusion
Binary search is a searching technique that follows the divide and conquer strategy. It is more efficient in comparison to other searching algorithms.
In this article, we have covered the working of binary search, its implementation in various programming languages as well as its application in the programming world. We have also discussed how binary search is different from linear search.