Searching Algorithms - Binary Search

Binary Search

Binary search is a simple search algorithm which works on the principle of Divide and Conquer. For this algorithm to work properly, the collection of data must be in sorted form.

This algorithm searches the sorted array by repeatedly dividing the search interval. Initially the search interval covers the whole array. If the search key matches the middle element of the interval, it returns the index of middle element. If the search key is less than the middle element, then the search interval is narrowed down to the lower half of the array. Otherwise it is narrowed down to upper half. This process is repeated until the search key is found or the search interval is empty.

For Example:
Consider the following array of sorted integers and the element to be searched is 20. Initially the length of search interval is equal to the length of entire array.

Now, the search key i.e. 20 is less than the middle element i.e. 35. Thus the search interval is narrowed down to lower half of the array.

Now, the search key is greater than the middle element i.e. 15. Thus the search interval is narrowed down to the upper half of current search interval.

Now, the search key is less than the middle element i.e. 25. Thus the search interval is narrowed down to the lower half of current search interval.

Finally the search key is equal to the middle element of the search interval. The index of middle element is returned and binary search is complete.

C Program:
Here is source code of the C Program to implement Linear Search. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

#include<stdio.h>

int binary_search(int elems[], int n, int x)
{
    int lower, higher, middle;

    lower = 0;
    higher = n-1;

    while (lower <= higher)
    {
        middle = (lower + higher)/2;
        if (elems[middle] < x)
        {
            lower = middle + 1;
        }
        else if (elems[middle] == x)
        {
            return middle;
        }
        else
        {
            higher = middle-1;
        }
    }

    return -1;
}

void main()
{
    int elems[20], n, x, i, pos;

    printf("Enter the numbers of elements: ");
    scanf("%d", &n);

    printf("Enter the elements of array: ");
    for (i=0; i<n; i++)
    {
        scanf("%d", &elems[i]);
    }

    printf("Enter the number to search: ");
    scanf("%d", &x);

    pos = binary_search(elems, n, x);

    if (pos == -1)
    {
        printf("%d is not present in the array.", x);
    }
    else
    {
        printf("%d is present at the position %d", x, pos+1);
    }
}

Output:

Enter the numbers of elements: 15
Enter the elements of array: 4
5
10
15
20
25
30
35
40
45
50
58
65
80
98
Enter the number to search: 20
20 is present at the position 5

Share on Google Plus

About AlgoStream

This is a short description in the author block about the author. You edit it by entering text in the "Biographical Info" field in the user admin panel.