Binary Search Algorithm

How does Binary Search Algorithm work?

The Binary Search Algorithm is an efficient method to search for an element in a sorted array or list. It works by repeatedly dividing the search interval in half. Here’s a detailed explanation of its working:

Initial Setup:

• The algorithm starts with two pointers, low and high, representing the lower and upper bounds of the array or list.
   
• These pointers help narrow down the search space. The low pointer starts at the beginning (index 0), and the high pointer starts at the end of the array (index n-1 where n is the length of the array).
   

Finding the Midpoint:

• In each iteration, the algorithm calculates the middle element of the array by finding the average of low and high:
  mid = (low + high) // 2
   
• This mid index helps divide the array into two halves.
   

Comparing the Target with Mid Element:

• If the target value (the element you're searching for) is equal to the middle element, the search is complete, and the index of the middle element is returned.
   
• If the target value is less than the middle element, the algorithm discards the right half of the array and continues searching in the left half by setting the high pointer to mid - 1.
   
• If the target value is greater than the middle element, the algorithm discards the left half and searches in the right half by setting the low pointer to mid + 1.
   

Repeating the Process:

• This process of calculating the midpoint and adjusting the pointers continues until either the target value is found, or the search space becomes invalid (i.e., low > high), in which case the target is not in the array, and the algorithm returns a failure or -1.
   

Time Complexity:

• Binary Search is highly efficient with a time complexity of O(log n) because it reduces the search space by half with each iteration. This makes it much faster than a linear search, especially for large datasets.

Binary Search Algorithm Example

Let’s take an example to understand the algorithm.

1. 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.
2. 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

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);
	}
}

You can also try this code with Online Java Compiler

Run Code

Python Implementation

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

	arr = [2, 5, 8, 9, 14]
	key = 9
	n= len(arr)
	res = binarySearch(arr, 0, n-1, key)

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

You can also try this code with Online Python Compiler

Run Code

Javascript Implementation

<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>

You can also try this code with Online Javascript Compiler

Run Code

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).

Applications of Binary Search Algorithm

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.

Disadvantages 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:

1. Start with a sorted array.
2. Define a range (low and high) to search within.
3. Repeat: Calculate mid-point.
4. Compare target with mid-point value.
5. Adjust the range (low/high) based on the comparison.
6. 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.
 

Recommended articles -

• Implement Linear Search and Binary Search in an Array
• Binary Search Vs Ternary Search
• Ternary Search