Data structures & algorithms (Beginner to Intermediate)

Free guided path13 chapters99+ problems

Earn badges and level up

Introduction

Do you want to know how to search for an element in the array with time complexity less than O(n)? This can be achieved by the binary search algorithm.

Binary Search is a searching algorithm to efficiently find a specific element in a monotonic array. An array is called monotonic if it is either non-increasing or non- decreasing. Binary search significantly reduces the search time from O(n) to O(logn).

Are you interested in knowing more about the implementation of binary search algorithm? Great! You are at the right place.

What is a Binary Search Algorithm?

A binary search algorithm is an algorithm to find an element’s position in a sorted array. It works by repeatedly dividing the search interval in half. If the element is found in the middle of the interval, the search is complete. Otherwise, the search continues on the half of the interval that does not contain the element and continues till the element is found or the search interval gets empty.

It has a time complexity of O(log n) because it eliminates half of the search interval at each step, making it a better choice than linear search which has O(n) time complexity.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Binary Search Algorithm Example

Let’s take an example to understand the algorithm.

For example, we have a sorted array as 2, 5, 8, 9, 14, and we want to search whether 9 is present or not. If 9 is present, then return its index; else return -1.

Initially, set the pointers low=0(start index of array) and high= size of array-1(last index of array)

3. Start your search using the middle element in the entire array, which is calculated as

int mid= low + (high-low)/2

Or

int mid = (low+high)/2

It is suggested to use the former formula as it is considered more efficient and prevents overflow. (high + low) , as in the latter case, can exceed the range and will eventually lead to overflow.

4. If the middle element equals the element you are searching for, then return the index of the middle element.

5. If the middle element is greater than the element you are searching for, then limit your search to the lower half(elements before the middle element).

6. If the above condition does not satisfy, then, if the middle element is smaller than the element you are searching for, then limit your search to the upper half(elements after the middle element).

7. Repeat steps 3-6 till low meets high.

Since 8(middle element) < 9(key), so consider the right half i.e. {9,14}.

Searching space has been reduced to the right half of the array. Again follow steps 3-6.

mid==9, which is the item to be searched. Thus we return the index of 9, i.e., 3.

How to Implement Binary Search?

There are two ways to implement the binary search algorithm:

Iterative Method

Recursive Method

Iterative Method

The iterative binary search method uses loops to perform the searches in the array. The steps involved in the iterative binary search are :

Initialize two pointers low(0) and high(size-1).

Declare a while loop which runs until the low pointer is less than or equal to the high pointer.

Inside the loop calculate the mid point of the high and low.

Check if the element present at the mid index is equal, greater or smaller than the required value.

PseudoCode

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

Recursive Method

The recursive approach follows the divide-and-conquer technique. This technique can be divided into the following three parts:

Divide: This involves dividing the main problem into smaller sub-problems.

Conquer: Call the function recursively to solve sub-problems until solved.

Combine the sub-problems to get the final answer to the main problem.

PseudoCode

binarySearch(arr, key, low, high)
if low > high
return false
else
mid = low + (high - low) / 2
if x == arr[mid]
return mid
/* x is on the right side */
else if x > arr[mid]
/* make a recursive call on the right half */
return binarySearch(arr, x, mid + 1, high)
/* x is on the left side */
else
/* make a recursive call on the left half */
return binarySearch(arr, x, low, mid - 1)

Implementation of Binary Search Algorithm

Java Implementation

java

java

class Main{ int binarySearch(int arr[], int low, int high, int key){ if (high >= low) { int mid = low + (high - low) / 2; /* If key found at mid, then return the index of mid */ if (arr[mid] == key) return mid;

/* Make a recursive call on the right half */ if (arr[mid] < key) return binarySearch(arr, mid+1, high, key);

/* Make a recursive call on the left half */ return binarySearch(arr, low, mid-1, key); }

/* Element not found, so return -1. */ return -1; }

public static void main(String args[]){

Main obj = new Main(); int arr[] = {2, 5, 8, 9, 14}; int key = 9; int n = arr.length; int res = obj.binarySearch(arr, 0, n - 1, key);

if (res == -1) System.out.println("The element " + key + " is not present in array"); else System.out.println("The element " + key + " is present in array at index " + res); } }

Python Implementation

Python

Python

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

#If key found at mid, then return the index of mid if arr[mid] == key: return mid

#make a recursive call on the right half elif arr[mid] < key: return binarySearch(arr, mid+1, high, key)

#make a recursive call on the left half else: return binarySearch(arr, low, mid-1, key) else: #Element not found, so return -1. return -1

if res != -1: print("The element is present at index % d" % res) else: print("The element is not present in the array")

Javascript Implementation

javascript

javascript

<script>

function binarySearch(arr, low, high, key){ if (high >= low) { let mid = low + Math.floor((high - low) / 2);

/* If key found at mid, then return the index of mid */ if (arr[mid] == key) return mid;

/* Make a recursive call on the right half */ if (arr[mid] < key) return binarySearch(arr, mid+1, high, key);

/* Make a recursive call on the left half */ return binarySearch(arr, low,mid-1, key); }

/* Element not found, so return -1. */ return -1; }

let arr = [ 2, 5, 8, 9, 14 ]; let key = 9; let n = arr.length let res = binarySearch(arr, 0, n - 1, key); (res != -1) ? document.write("Element is present at index " +res): document.write( "Element is not present in array");

</script>

Binary Search Algorithm Complexity

Time Complexity

In each binary search iteration, we change the range from low to mid or mid to high. This means we effectively reduce the search space by half. Hence the time complexity for the binary search algorithm is O(logn).

Space Complexity

We only use two extra variables, low and mid, to store the start and the end pointers, respectively. Hence the space complexity for binary search is O(1).

Binary Search Algorithm Applications

Due to its considerably lower time complexity, Binary Search has many applications in computer science. Some of these applications are discussed below.

Searching in Sorted Lists: The main application of the binary search algorithm is to search for elements in sorted arrays. This algorithm is much faster than the traditional linear search algorithm.

Game Development: Binary Search is used in the game development domain for collision detection and path-finding tasks. This algorithm helps to efficiently search for objects in games and increase the response time.

Machine Learning: Binary Search is also used in the machine learning domain to build complex algorithms to train neural networks, find parameters for a model, etc.

Mathematics: Binary Search is also used in mathematics for solving equations. Binary Search is used in mathematics to find roots of equations, maxima and minimal, etc.

Advantages of Binary Search

Efficiency: Binary search is highly efficient for large sorted datasets, as it divides the search space in half with each comparison.

Fast Retrieval: It provides quick access to the desired element, especially in sorted arrays or lists.

Consistent Performance: Binary search maintains consistent time complexity (O(log n)) for a wide range of input sizes.

Low Memory Usage: It requires minimal additional memory, primarily for storing indices or pointers.

Deterministic: Binary search always finds the desired item or identifies its absence.

Reduced Comparisons: Typically requires fewer comparisons than linear search algorithms, resulting in faster search times.

Applicability: Suitable for searching in both arrays and balanced binary trees.

Divide and Conquer: Binary search follows the divide-and-conquer strategy, making it easy to implement recursively.

Drawbacks of Binary Search

Sorted Data Requirement: Binary search necessitates that the data is sorted beforehand. If the data isn't sorted, a separate sorting step is required, which adds time complexity.

Inefficient for Unsorted Data: In unsorted datasets, binary search is not suitable, and linear search can be more efficient.

Additional Memory: In some implementations, binary search may require additional memory for maintaining indices or pointers.

Lack of Flexibility: It's less flexible when compared to linear search algorithms, which can handle unsorted and dynamically changing data.

Complexity: While binary search is efficient, its implementation can be more complex than linear search algorithms.

Limited Applicability: Binary search is primarily useful for searching in ordered arrays or lists and may not be the best choice for other data structures.

Not Suitable for Partial Matches: Binary search is designed to find exact matches, making it less suitable for tasks like fuzzy searching or pattern matching.

Frequently Asked Questions

What is the algorithm of binary search?

Binary search algorithm:

Start with a sorted array.

Define a range (low and high) to search within.

Repeat: Calculate mid-point.

Compare target with mid-point value.

Adjust the range (low/high) based on the comparison.

Repeat until the target is found or the range is empty.

What is binary search algorithm in Java?

Binary search in Java is a divide-and-conquer algorithm to search for an element in a sorted array. Using Arrays.binarySearch(arr, key), it returns the index of 'key' or a negative value if not found. It's efficient for large sorted datasets and is part of Java's standard library in the Arrays class.

Where is binary search algorithm used?

Binary search is used in various applications, including searching in sorted arrays, databases, and directories. It's common in computer science, data structures, and information retrieval systems for efficient data lookup.

Conclusion

This article has explained the binary search algorithm and explored iterative and recursive approaches of binary search algorithm along with their codes. We also explored its implementation in different languages and discussed time and space complexity. Finally, some frequently asked questions are discussed.