Binary Search

Binary search is also known as half-interval search or logarithmic search. It is a searching algorithm used to find the position of an element in the sorted array. The payoff for using a sorted array comes when we use a binary search. This kind of search is much faster than a linear search, especially for large arrays.

It uses the same approach you did when you were kid (if you were smart) and playing Number Guess game. In this game, a friend asks you to guess a number that he is thinking of between 1 and 10. When you guess a number, he tell you one of the three things i.e., whether your guess is larger than the number that he thinks, or its smaller or you guessed correctly.

If you were smart kid, to find the number in the fewest guesses, you should always start by guessing 5. If your friend says the number that you guessed is too high, then you assume the number is between 1 and 4. Then your next guess would be 2 (half way between 1 and 4). If he says too low, then your next guess would be 3 which is correct answer. Please refer the following table shows an example of a game session when the number to be guessed is 3.

Number Guess Game

[table id=8 /]

So the binary search compares the target element to the middle element of the array. If they are not equal, the half in which the target element cannot lie will be eliminated and the search will continue on the remaining half, again taking the middle element  of the remaining half to compare to the target element, and repeating this until the target element is found. If the search ends with the remaining half being empty, the target element is not in the array.

Binary Search Example

package com.sneppets.dsalgo;

//Iterative binary search example
public class BinarySearchExample {
	
	public int binarySearch(int array[], int element){
		
		int lBound = 0;
		
		int uBound = array.length-1;
		
		while(lBound <= uBound){
			
			int mid = (lBound + uBound)/2;
			
			//check if element is present at the mid
			if(element == array[mid]){
				return mid;
			}
			
			//if element is greater than mid, then ignore left half sub array
			if(element > array[mid]){
				
				lBound = mid + 1;
			}
			//else the element is smaller than mid, ignore right half sub array
			else {
				uBound = mid - 1;
			}
		}
		
		//if we reach here, it means the element 
		//is not present in the array
		return -1;
		
	}
	
	public static void main (String args[]){
		
		BinarySearchExample obj = new BinarySearchExample();
		int array[] = {10, 20, 30, 40, 50};
		int result = obj.binarySearch(array, 20);
		if(result == -1){
			System.out.println("Element not present in the array");
		}
		else {
			System.out.println("Element found at index " + result);
		}
	}

}

Time Complexity Analysis

In order to understand time complexity of binary search, please go through this sneppet How to calculate binary search complexity

So binary search runs in logarithmic time in the worst case you need to make O(log n) comparisons. where n is the number of elements in the array, the O is Big O notation, and log is the logarithm. Algorithms taking logarithmic time are commonly found in operations on binary trees or when using binary search.

Space Complexity Analysis

Binary search takes constant O(1) space, meaning that the space taken by the algorithm is the same for any number of elements in the array.

A space complexity of O(1) means that the space required by this binary algorithm using iterative approach to process data is constant and it does not grow with the size of the data on which the algorithm is operating.

Conclusion

Binary search is faster than linear search (Please check Linear Search Time and Space Complexity Analysis) except for small arrays, but the array must be sorted first.