# Binary Search in Data Structures

06 Jun 2024
Intermediate
12.3K Views
Learn via Video Course & by Doing Hands-on Labs

## Binary Search: An Overview

In the previous tutorial, we saw that linear search is inefficient for large and sorted arrays as it ends up searching the entire array to find an element. It becomes time-consuming. To overcome this limitation of the linear search algorithm, we have the `binary search` technique with us.

In this DSA tutorial, we are going to look in detail at the Binary Search. We will learn its features, working, implementation, etc. To further enhance your understanding and application of binary search concepts, consider enrolling in the best Data Structures And Algorithms Certification to gain comprehensive insights into effective data structure utilization for improved problem-solving and time management.

## What is Binary Search in Data Structures?

It is a searching algorithm that searches for an element's position in a sorted array only. If the elements are not sorted already, we need to sort them first to apply the binary search technique. Sorted here means that the elements will either be in a natural increasing or decreasing order.

This search technique involves dividing a large dataset into smaller subsets until the desired item is found. It repeatedly divides in half the portion of the list and tries to find the element in one or the other half until the element is found or the array is exhausted. Thus, the element is always searched in the middle portion of an array

### Binary Search Algorithm

``````Step: 1 Start by defining the search interval/space: the entire array or list in the beginning.
Step: 2 Divide the search space into two halves by finding the midpoint.
Step: 3 Compare the middle element of the search space with the key.
Step: 4 If the key matches with the middle element, the search is complete and the index of the value is returned. The process is terminated.
Step: 5 If the key does not match with the middle element, choose which half will be used as the next search space.
If the key is smaller than the middle element, the left half is used for the next search.
If the key is larger than the middle element, the right side is used for the next search.
Step: 7 This process is continued until the key is found or the total search space is exhausted.    ``````

### Working of Binary Search Algorithm in Data Structures

Let's suppose we need to find the element 17 i.e. key=17 in the given array or list. We will work according to the above-given algorithm.
1. Set two pointers low and high at the lowest and the highest positions respectively.

2. Find the middle element mid of the array ie. arr[(low + high)/2] = arr[(0+6)]/2] = arr[3] = 44

3. If the element key == mid, return the index of mid. Otherwise, compare the element to be searched with mid.
• If key > mid, compare the key with the middle element of the elements on the right side of mid. This is done by setting low to low = mid+1.
• Otherwise, compare the key with the middle element of the elements on the left side of mid. This is done by setting high to high = mid-1.

4. Repeat steps 2 to 3 until low meets high.

5. key = 17 is found.

## Implementation of Binary Search Algorithm in Different Programming Languages

There are mainly two ways to implement the Binary Search Algorithm in Data Structures, using recursion and iteration. Let us look at each of them.

### Recursive Binary Search

It follows the divide and conquer approach.

#### Recursive Binary Search Algorithm

``````binarySearch(arr, key, low, high)
if low > high
return False
else
mid = (low + high) / 2
if key == arr[mid]
return mid
else if key > arr[mid]        // key is on the right side
return binarySearch(arr, key, mid + 1, high)
else                               // key is on the left side
return binarySearch(arr, key, low, mid - 1)    ``````

#### Example of Recursive Binary Search Algorithm in Different Languages

``````
def binarySearch(array, key, low, high):
if high >= low:
mid = low + (high - low) // 2

# If found at mid, then return it
if array[mid] == key:
return mid

# Search the left half
if array[mid] > key:
return binarySearch(array, key, low, mid - 1)

# Search the right half
return binarySearch(array, key, mid + 1, high)

return -1

array = [4, 17, 32, 44, 75, 80, 86]
print("The array to be searched is: ", array)

key = 80
n = len(array)
result = binarySearch(array, key, 0, n - 1)

if result == -1:
else:
print("Element is found at index", result)
``````
``````
import java.util.Arrays;

public class BinarySearch {
static int binarySearch(int[] array, int key, int low, int high) {
if (high >= low) {
int mid = low + (high - low) / 2;

// If found at mid, then return it
if (array[mid] == key) {
return mid;
}

// Search the left half
if (array[mid] > key) {
return binarySearch(array, key, low, mid - 1);
}

// Search the right half
return binarySearch(array, key, mid + 1, high);
}

return -1;
}

public static void main(String[] args) {
int[] array = {4, 17, 32, 44, 75, 80, 86};

System.out.print("The array to be searched is: ");
System.out.println(Arrays.toString(array));

int key = 80;
int n = array.length;
int result = binarySearch(array, key, 0, n - 1);

if (result == -1) {
} else {
System.out.println("Element is found at index " + result);
}
}
}
``````
``````

#include <iostream>
using namespace std;

int binarySearch(int array[], int key, int low, int high) {
if (high >= low) {
int mid = low + (high - low) / 2;

// If found at mid, then return it
if (array[mid] == key)
return mid;

// Search the left half
if (array[mid] > key)
return binarySearch(array, key, low, mid - 1);

// Search the right half
return binarySearch(array, key, mid + 1, high);
}

return -1;
}

int main(void) {
int array[] = {4, 17, 32, 44, 75, 80, 86};
cout << "The array to be searched is: ";
for (int i : array) {
cout << i << ", ";
}
cout << std::endl;
int key = 80;
int n = sizeof(array) / sizeof(array[0]);
int result = binarySearch(array, key, 0, n - 1);
if (result == -1)
else
printf("Element is found at index %d", result);
``````

#### Output

``````The array to be searched is: 4, 17, 32, 44, 75, 80, 86,
Element is found at index 5 ``````

### Iterative Binary Search

This iterative implementation of the binary search algorithm involves a loop to keep dividing the search space in half until the target value is found or the search space is empty.

#### Iterative Binary Search Algorithm

``````do until the pointers low and high meet each other.
mid = (low + high)/2
if (x == arr[mid])
return mid
else if (x > arr[mid]) // x is on the right side
low = mid + 1
else                       // x is on the left side
high = mid - 1 ``````

#### Example of Iterative Binary Search Algorithm in Different Languages

``````
def binarySearch(array, key, low, high):
while low <= high:
mid = low + (high - low) // 2

if array[mid] == key:
return mid

if array[mid] < key:
low = mid + 1
else:
high = mid - 1

return -1

array = [4, 17, 32, 44, 75, 80, 86]
print("The array to be searched is:", end=" ")
print(*array, sep=", ")
key = 32
result = binarySearch(array, key, 0, len(array) - 1)
if result == -1:
else:
print(f"Element {key} is found at index {result}")
``````
``````
public class BinarySearch {
static int binarySearch(int[] array, int key, int low, int high) {
while (low <= high) {
int mid = low + (high - low) / 2;

if (array[mid] == key)
return mid;

if (array[mid] < key)
low = mid + 1;
else
high = mid - 1;
}

return -1;
}

public static void main(String[] args) {
int[] array = {4, 17, 32, 44, 75, 80, 86};
System.out.print("The array to be searched is: ");
for (int i : array) {
System.out.print(i + ", ");
}
System.out.println();
int key = 32;
int result = binarySearch(array, key, 0, array.length - 1);
if (result == -1)
else
System.out.println("Element " + key + " is found at index " + result);
}
}
``````
``````
#include <iostream>
using namespace std;

int binarySearch(int array[], int key, int low, int high) {
while (low <= high) {
int mid = low + (high - low) / 2;

if (array[mid] == key)
return mid;

if (array[mid] < key)
low = mid + 1;
else
high = mid - 1;
}

return -1;
}

int main(void) {
int array[] = {4, 17, 32, 44, 75, 80, 86};
cout << "The array to be searched is: ";
for (int i : array) {
cout << i << ", ";
}
cout << endl;
int key = 32;
int n = sizeof(array) / sizeof(array[0]);
int result = binarySearch(array, key, 0, n - 1);
if (result == -1)
else
printf("Element %d is found at index %d", key, result);

return 0;
}
``````

#### Output

``````The array to be searched is: 4, 17, 32, 44, 75, 80, 86,
Element 32 is found at index 2   ``````

## Binary Search Complexity Analysis

1. Time Complexity
 Case Time Complexity Best Case `O(1)` Average Case `O(log n)` Worst Case `O(log n)`
2. Space Complexity: As we are not using any significant extra memory in Binary Search, the space complexity is constant, i.e. `O(1)`.

## Applications of Binary Search

1. In libraries of Java, .Net, C++ STL.
2. The binary search is used to pinpoint the place where the error happens while debugging.
3. It can serve as a building block for complicated machine learning algorithms, such as those for training neural networks.
4. It can be used to search in computer graphics algorithms like ray tracing or texture mapping.
5. It can be applied to database searches.

1. It is faster than linear search, especially for large arrays since its run time complexity is `O(logN)`.
2. More efficient than other searching algorithms with a similar time complexity, such as interpolation search or exponential search.
3. At each iteration, the binary search algorithm eliminates half of the list and significantly reduces the search space.
4. Binary search is well-suited for searching large datasets that are stored in external memory, such as on a hard drive or in the cloud.
5. It even works on a rotated array.

1. Binary search requires that the array be sorted before the algorithm is applied. If the array is not sorted, then the algorithm cannot be used.
2. Binary search requires that the data structure being searched be stored in contiguous memory locations.
3. If the array is being updated dynamically, i.e., new elements are added or old elements are deleted, then the binary search cannot be used as it requires the array to be static.
4. It requires that the elements of the array be comparable, meaning that they must be able to be ordered.
5. The recursive binary search method uses stack space.
##### Summary
So, here we saw every aspect of the binary search algorithm in data structures. It must not have been that difficult to understand as compared to linked lists or doubly linked lists. Just make sure you are thorough with arrays in data structures. To apply your knowledge of linear search algorithms, enroll in our Best Dsa Course.
Share Article

### Live Classes Schedule

Our learn-by-building-project method enables you to build practical/coding experience that sticks. 95% of our learners say they have confidence and remember more when they learn by building real world projects.
 Generative AI For Software Developers Jul 20 SAT, SUN Filling Fast 08:30PM to 10:30PM (IST) Angular Certification Course Jul 20 SAT, SUN Filling Fast 06:00PM to 08:00PM (IST) Azure Master Class Jul 20 SAT, SUN Filling Fast 03:00PM to 05:00PM (IST) ASP.NET Core Certification Training Jul 28 SAT, SUN Filling Fast 07:00AM to 09:00AM (IST) Software Architecture and Design Training Jul 28 SAT, SUN Filling Fast 05:30PM to 07:30PM (IST) .NET Solution Architect Certification Training Jul 28 SAT, SUN Filling Fast 05:30PM to 07:30PM (IST) Azure Developer Certification Training Jul 28 SAT, SUN Filling Fast 10:00AM to 12:00PM (IST) Advanced Full-Stack .NET Developer Certification Training Jul 28 SAT, SUN Filling Fast 07:00AM to 09:00AM (IST) Data Structures and Algorithms Training with C# Jul 28 SAT, SUN Filling Fast 08:30PM to 10:30PM (IST) Angular Certification Course Aug 11 SAT, SUN Filling Fast 09:30AM to 11:30AM (IST) ASP.NET Core Project Aug 24 SAT, SUN Filling Fast 07:00AM to 09:00AM (IST)

Can't find convenient schedule? Let us know

Similar Articles