A binary search algorithm finds the position of the target element in a sorted array. It compares the target element with the middle element of the array.

Binary search exhibits better timing behavior for large volumes of data with timing complexity O(log2n)

Binary search is a search technique that works efficiently on sorted lists.

Binary search uses the divide and conquer strategy, in which the list is divided into two halves, with the item being compared with the middle element of the list.

If a match is found, the location of the middle element is returned. Otherwise, we search into either of the halves depending on the result produced through the match.

Time Complexity

Best Case O(1): It occurs when the element to be searched is found in the first comparison. That is the first middle element itself is the element to be searched

Average Case O(log n): Binary search has an average case time complexity of O(log n)

Worst Case O(log n): The worst case occurs in Binary search when we have to keep reducing the search space until it contains only one element.

The binary search has a time complexity of O(log n)

Space Complexity

Example

#include <stdio.h>  
int binary_search(int a[], int beg, int end, int key) {    
    int mid;    
    if(end >= beg) {        
        mid = (beg + end) / 2;    
        
        /* if the item to be searched is present at middle */  
        if(a[mid] == key)    
            return mid + 1;       
        
        /* if the item to be searched is smaller than middle, then it can only be in left sub-array */  
        else if(a[mid] < key)     
            return binary_search(a, mid + 1, end, key);     
        
        /* if the item to be searched is greater than middle, then it can only be in right sub-array */  
        else     
            return binary_search(a, beg, mid - 1, key); 
    }    
    return -1;     
}   

int main() {  
    // The given array  
    int a[] = {11, 14, 25, 30, 40, 45, 60, 65, 90}; 
    
    // The value to be searched  
    int key = 45; 
    
    // The size of array  
    int n = sizeof(a) / sizeof(a[0]); 
    
    // Store the result  
    int result = binary_search(a, 0, n-1, key); 
    
    printf("The elements of the array are - ");  
    for (int i = 0; i < n; i++)  
        printf("%d ", a[i]);   
    
    printf("nElement to be searched is - %d", key);  
    if (result != -1)  
        printf("nElement is present at %d position of array", result);  
    else  
        printf("nElement is not present in the array");  
        
    return 0;  
}

Java Program

public class BinarySearch {  
    static int binarySearch(int a[], int beg, int end, int key) {    
        int mid;    
        if(end >= beg) {  
            mid = (beg + end) / 2;
            
            /* if the item to be searched is present at middle  */  
            if(a[mid] == key)    
                return mid + 1;   
            /* if the item to be searched is smaller than middle, then it can only  
be in left sub-array */  

            else if(a[mid] < key)     
                 return binarySearch(a, mid + 1, end, key);    
                 
            /* if the item to be searched is greater than middle, then it can only be  
in right sub-array */  
            else    
                return binarySearch(a, beg, mid - 1, key);   
        }    
        return -1;    
    }   
    
    public static void main(String args[]) {  
        // The given array
        int a[] = {11, 14, 25, 30, 40, 45, 60, 65, 90};   
        
        // The value to be searched  
        int key = 60; 
        
        // The size of array  
        int n = a.length; 
        
        // Store the result  
        int result = binarySearch(a, 0, n - 1, key); 
        
        System.out.print("The elements of the array are: ");  
        for (int i = 0; i < n; i++)  
            System.out.print(a[i] + " ");  
            
        System.out.println();  
        System.out.println("Element to be searched is: " + key);  
        if (result != -1)  
            System.out.println("Element is present at " + result + " position of array");  
        else  
            System.out.println("Element is not present in the array");  
    }  
}