Home » C programs » C one-dimensional array programs

C Program to Search Sorted Array using Binary Search

Here, we are going to learn how to perform binary search on a sorted array: Here, a sorted array is given and we have to perform binary search on it.
Submitted by Radib Kar, on December 12, 2018

Problem statement

Write a c program that will take input a sorted array and to binary search to find the element to be searched. (Output proper prompt messages in case element not found).

Algorithm

Binary search actually divides the entire array into two halves at each iteration and do the search in one half based on the searching element since the array is sorted.

Let,

• Starting index=0
• End index=n-1, where n is the array length
• Middle index= (start + end index)/2= (n-1)/2, this middle index divides the array into two half
• If array[middle]==search value
• We are done
• Else if array [middle] < search value
• Then we need to search in the upper half
• Else if array [middle]>search value
• Then we need to search in the lower half
• These three cases need to be handled recursively to implement a binary search.
• Clearly, these searching method is possible due to the sorted input array.

Function definition (Pseudo code)

We can build up a recursive binSearch()function which will do the binary search.

Function binSearch(input array,start index, end index,search value)
    middle index=(start index + end index)/2;    
    //if search value found return position(1-indexed position)
    IF array[middle index] == search value
        return middle index+1;
    //if search value>array[middle index], search in the segment 
    //(middle index+1,end index), i.e., the upper half & 
    //search until start index==end index 
    ELSE IF (search value>array[middle index] &start index!= end index)
        return binSearch(input array,middle index+1,end index,search value);//recursive call
    //if search value<array [middle index] search in the segment 
    //(start index, middle index-1), i.e., the lower half& search until start index== end index
    ELSE IF(search value<array[middle index] &start index!= end index)
        return binSearch(input array, start index,middle index-1,seach value);
    //search value not found as start index == end index
    ELSE
    return 0;
END Function

Example & Explanation

Let the input array be:
2 5 8 9 12 13 16, length, n=7
Search element: 5

//In main function:
    
Make call binSearch(array, 0,7,5)
binSearch (array, 0, 7, 5)
middle index =(0+7)/2=3
array[3]!=5
array[3]>5&& 0<7
    
make callbinSearch(array, 0, 3-1)
binSearch(array, 0, 3-1)
middle index =(0+2)/2=1
array[1]==5
return (1+1) //position 2
    
Program terminated

C Program to Search Sorted Array using Binary Search

#include <stdio.h>
#include <stdlib.h>

// binary search implementation using recursion
int binSearch(int* a, int first, int last, int t) {
  // find middle index
  int mid = (first + last) / 2;
  // if data found return position(1-indexed position)
  if (a[mid] == t) return mid + 1;
  // if data > a[mid] search in the segment (mid+1,last)
  else if (t > a[mid] & first != last)  // search until first!=last
    return binSearch(a, mid + 1, last, t);
  // if data < a[mid] search in the segment (first,mid-1)
  else if (t < a[mid] & first != last)
    return binSearch(a, first, mid - 1, t);
  else
    return 0;
}

int main() {
  int n, t;
  printf("enter number of array elements: ");
  scanf("%d", &n);

  int* a = (int*)(malloc(sizeof(int) * n));

  printf("enter elements: \n");
  // input array elements
  for (int i = 0; i < n; i++) scanf("%d", &a[i]);

  printf("enter element to search\n");
  scanf("%d", &t);
  // output result
  if (binSearch(a, 0, n - 1, t))
    printf("\n%d found at position %d\n", t, binSearch(a, 0, n - 1, t));
  else
    printf("\n%d not found\n", t);

  return 0;
}

Output

Output (first run)

enter number of array elements: 7
enter elements:
2 5 8 9 12 13 16
enter element to search
5

5 found at position 2

Output (second run)

enter number of array elements: 6
enter elements:
11 34 45 56 67 78
enter element to search
20

20 not found

C One-Dimensional Array Programs »