Binary Search

Binary search technique is very fast and efficient. It requires the list of elements to be in sorted order.

In this method, to search an element we compare it with the element present at the center of the list. If it matches then the search is successful otherwise, the list is divided into to halves one from the 0^thelement to the center (first half), another from the center element to the last element (second half). As a half all the elements in first half are smaller than center element whereas all the elements in second half are greater.

The searching will now proceed in either of the two halves depending upon whether the target element is greater or smaller than the center element. If the element is smaller than the center element then the searching is done in the first half, else done in second half.

The process of comparing the required element with the center element and if not found then dividing the elements into two halves is repeated till the element is found or the division of half parts gives one element.

Example The active part of search is underlined.

List i j mid Result of comparison

12 18 25 36 45 48 50 1 7 4 45>36 : Right part

12 18 25 36 45 48 50 5 7 6 45<48 : Left part

12 18 25 36 45 48 50 5 6 5 45=45 : Found

Listing: Following program is showing the implementation of binary search using recursion and its operations.

/* 
* C Program to Perform Binary Search using Recursion 
*/ 
#include <stdio.h> 

void binary_search(int [], int, int, int); 
void bubble_sort(int [], int); 

int main() 
{ 
    int key, size, i; 
    int list[25]; 

    printf("Enter size of a list: "); 
    scanf("%d", &size); 
    printf("Generating random numbers\n"); 
    for(i = 0; i < size; i++) 
    { 
        list[i] = rand() % 100; 
        printf("%d  ", list[i]); 
    } 
    bubble_sort(list, size); 
    printf("\n\n"); 
    printf("Enter key to search\n"); 
    scanf("%d", &key); 
    binary_search(list, 0, size, key); 

} 

void bubble_sort(int list[], int size) 
{ 
    int temp, i, j; 
    for (i = 0; i < size; i++) 
    { 
        for (j = i; j < size; j++) 
        { 
            if (list[i] > list[j]) 
            { 
                temp = list[i]; 
                list[i] = list[j]; 
                list[j] = temp; 
            } 
        } 
    } 
} 

void binary_search(int list[], int lo, int hi, int key) 
{ 
    int mid; 

    if (lo > hi) 
    { 
        printf("Key not found\n"); 
        return; 
    } 
    mid = (lo + hi) / 2; 
    if (list[mid] == key) 
    { 
        printf("Key found\n"); 
    } 
    else if (list[mid] > key) 
    { 
        binary_search(list, lo, mid - 1, key); 
    } 
    else if (list[mid] < key) 
    { 
        binary_search(list, mid + 1, hi, key); 
    } 
}

} 

Output: 
    Enter size of a list: 10 
    Generating random numbers 
    83  86  77  15  93  35  86  92  49  21  
     
    Enter key to search 
    21 
    Key found