This method works on sorted lists by progressively making better guesses to find the location of a search key.

Illustration

Consider the following array:

3 10 15 20 35 40 60

Suppose we want to search the element "15"

  1. We take beg = 0, end = 6 and compute the location of the middle element as
    mid = (beg+end)/2 = (0+6)/2 = 3
  2. We then compare the search key with mid i.e. a[mid]=a[3] is not equal to 15. Since beg<end, we start the next iteration.
  3. As a[mid]=20>15, therefore, we take end = mid-1 = 3-1 = 2 whereas beg remains the same.. Thus
    mid = (beg+end)/2 = (0+2)/2 =1
  4. Since a[mid] i.e. a[1]=10<15, therefore, we take beg=mid+1=1+1=2, while end remains the same.
  5. Now beg=end. Compute the mid element:
    mid = (beg+end)/2 = (2+2)/2 = 2
    Since a[mid] i.e. a[2]=15, the search terminates on success.

Algorithm

Binarysearch(a,n,item,loc)

Begin
set beg=0
set end=n-1
set mid=(beg+end)/2
while((beg<=end) and(a[mid]!=item) do
if(item<a[mid]) then
set end=mid-1
else
set beg=mid+1
endif
set mid=(beg+end)/2
endwhile
if(beg>end) then
set loc=-1
else
set loc=mid
endif
end

C/C++ Implementation

.cf { font-family: Lucida Console; font-size: 9pt; color: black; background: white; } .cl { margin: 0px; } .cb1 { color: green; } .cb2 { color: blue; } .cb3 { color: maroon; }

int binarysearch(int a[], int n, int key)
{
    int beg,end,mid;
    beg=0; end=n-1;
    mid=(beg+end)/2;
    while((beg<=end)&&(a[mid]!=key))
    {
        if(key<a[mid])
            end=mid-1;
        else
            beg=mid+1;
        mid=(beg+end)/2;
    }
    if(beg>end)
        return -1;
    else
        return mid;
}

Analysis of Binary Search

In each iteration, the search is reduced to one-half of the array. For n elements in the array, there will be a maximum of log2 n iterations.

Thus, the complexity of binary search is O(log2 n).

Complete Program Listing

/**
 * Program that illustrates the working of Binary Search
 * http://www.byteguide.com
 */
 
#include <stdio.h>
 
int binarysearch(int a[], int n, int key)
{
    int beg,end,mid;
    beg=0; end=n-1;
    mid=(beg+end)/2;
    while((beg<=end)&&(a[mid]!=key))
    {
        if(key<a[mid])
            end=mid-1;
        else
            beg=mid+1;
        mid=(beg+end)/2;
    }
    if(beg>end)
        return -1;
    else
        return mid;
}
 
int main()
{
    int arr[50], n, key, index;
 
    printf("How many elements do you want to create the array with?(max 50): ");
    fflush(stdout);
 
    scanf("%d", &n);
 
    puts("Enter the array elements in ascending order");
    for (index = 0; index < n; index++)
        scanf("%d", &arr[index]);
 
    printf("Enter the search key: ");
    fflush(stdout);
 
    scanf("%d", &key);
 
    index = binarysearch(arr, n, key);
 
    if (index == -1)
        puts("Sorry, the given key was not found");
    else
        printf("The given key was found at index:%dn", index);
 
    return 0;
}