Register | Sing In

New posts

Stacks in C programming Linked Lists in C programming File Input/Output in C programming Check prime numbers in C Programming C Programming Enumeration C Programming Union

Archives

2013-10 2013-09 2013-08

Searching an Array with Binary Search in C Programming

August 26, 2013 Posted by: GPA Views: 1892 0 comments

Problem

Write Binary Search in C Programming.

Solution

 The linear searching method is used for small or unsorted arrays. But for large arrays linear searching is not optimal algorithm. If the array is sorted, the binary search algorithm can be used.

The algorithm locates the middle element of the array and compares it to the search value. If they are equal, the search value is found and the index of that element is returned. If they are not equal, the problem is reduced to searching one-half of the array. If the search value is less than the middle element of the array the first half of the array is searched, otherwise the second half of the array is searched. If the search value is not found in the specified subarray, the algorithm is repeated. The search continues until the search value is equal to the middle element of a subarray, or until the subarray consists of one element that is not equal to the search value.

Example:

   

#include <stdio.h>
#include <stdlib.h>
int input_array[8] = {1, 5, 12, 56, 70, 80, 82, 94};//input array
int size=8;
int binarySearch(int key, int low, int high);
int main(int argc, char *argv[])
{
     int i,j,k;
     int key;//search value
     printf( "globalproganswer.com\n" );
     printf( "Array: " );
     for ( i = 0; i < size; i++ ) {
        printf( "%d ",input_array[i]);
     }
     printf( "\nEnter search value: " );
     scanf("%d",&key);
   if(binarySearch(key,0,8)!=-1){
        printf("Index of search value is %d",binarySearch(key,0,8));
   }else{      
printf("No such element");
    }  
   printf("\n");
   system("PAUSE");
return 0;
}
//function binarySearch
int binarySearch(int key, int low, int high) {
      if (low > high) return -1;
      int mid = low + (high - low) / 2;
      if (key < input_array[mid]) {
             return binarySearch(key, low, mid - 1);//call function binarySearch recursively
     } else if (key > input_array[mid]) {
             return binarySearch(key, mid + 1, high);
      } else {
           return mid;//return index of search value
       }
}

Output

 binary search in c

Download this example


0 Comments...

Leave a Reply

Please, Sing In to leave a Reply for this material.



Online Chat

LiveZilla Live Help

Popular posts

Function strtok in C programming Check prime numbers in C Programming C Programming Union Linked Lists in C programming File Input/Output in C programming C Programming Enumeration

RSS-subscribe

New materials

Subscribe