Like Us On Facebook

Follow Us On Twitter

Drop Down Menu

Saturday 16 March 2013

Binary Search In An Array Algorithm And C Code

As I have already described what are Arrays and their basic creation C code, in this post, we'll learn how to perform Binary Search In An Array, its Algorithm And C Code.

In computer science, a binary search or half-interval search algorithm finds the position of a specified value (the input "key") within a sorted array. In each step, the algorithm compares the input key value with the key value of the middle element of the array. If the keys match, then a matching element has been found so its index, or position, is returned. Otherwise, if the sought key is less than the middle element's key, then the algorithm repeats its action on the sub-array to the left of the middle element or, if the input key is greater, on the sub-array to the right. If the remaining array to be searched is reduced to zero, then the key cannot be found in the array and a special "Not found" indication is returned.
A binary search halves the number of items to check with each iteration, so locating an item (or determining its absence) takes logarithmic time. A binary search is a dichotomic divide and conquer search algorithm.

Algorithm/Pseudo-code:

Recursive Algorithm

A straightforward implementation of binary search is recursive. The initial call uses the indices of the entire array to be searched. The procedure then calculates an index midway between the two indices, determines which of the two subarrays to search, and then does a recursive call to search that subarray.

Each of the calls is tail recursive, so a compiler need not make a new stack frame for each call. The variables imin and imax are the lowest and highest inclusive indices that are searched.
int binary_search(int A[], int key, int imin, int imax)
{
  // test if array is empty
  if (imax < imin):
    // set is empty, so return value showing not found
    return KEY_NOT_FOUND;
  else
    {
      // calculate midpoint to cut set in half
      int imid = midpoint(imin, imax);
 
      // three-way comparison
      if (A[imid] > key)
        // key is in lower subset
        return binary_search(A, key, imin, imid-1);
      else if (A[imid] < key)
        // key is in upper subset
        return binary_search(A, key, imid+1, imax);
      else
        // key has been found
        return imid;
    }
}

It is invoked with initial imin and imax values of 0 and N-1 for a zero based array.
The number type "int" shown in the code has an influence on how the midpoint calculation can be implemented correctly. With unlimited numbers, the midpoint can be calculated as "(imin + imax) / 2"

C Code For Binary Search:

/* Double-Click To Select Code */

#include<stdio.h>
#include<conio.h>
void main()
{
 int arr[10], num, i, n, found=0, pos=-1, beg, end, mid;
 clrscr();

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

 printf("\nEnter the number that has to be searched: ");
 scanf("%d",&num);

 beg=0;
 end=n-1;
 while(beg<=end)
 {
  mid=(beg end)/2;
  if(arr[mid]==num)
  {
   printf("\n %d is present in the array at position = %d",num,mid);
   found=1;
   break;
  }

  if(arr[mid] > num)
  end = mid-1;

  else if(arr[mid] < num)
  beg = mid+1;
 }

 if(beg > end && found==0)
 printf("\n %d does not exist in the array",num);
 getch();
}

This Code Is Quite Easy. First we take the no. of elements from the user and then user enter them. Then user inputs the element that has to be searched. Then we begin the searching. If the element to be found is the middle element, the element is shown, other wise for the two conditions, arr[mid] > num or arr[mid]  < num, the search iterates, either till the element is found or until the array gets terminated.  


Output:

Binary Search C Code


Please Comment If You Liked This Post !! 

This article uses material from the Wikipedia article Binary search algorithm which is released under the Creative Commons Attribution-Share-Alike License 3.0


Do you like this post? Please link back to this article by copying one of the codes below.

URL: HTML link code: Forum link code: