Skip to main content

ProwessApps

Learn · Practice · Excel
About Contact
Login / Register

C Program to search an element in Array using "Binary Search".

C Code Example — Data Structure Programs

ADVERTISEMENT

C Program to search an element in Array using "Binary Search".

Objective

Write a C program to search for an element in an Array using Binary Search.

Algorithm / Approach

  1. Initialize a PRE-SORTED array in ascending order.
  2. Read the target number n.
  3. Set beg = 0 and end = size - 1.
  4. Loop while beg <= end.
  5. Calculate mid = (beg + end) / 2.
  6. If ar[mid] == n, the item is found. Break the loop.
  7. If ar[mid] < n, the target is in the right half, so set beg = mid + 1.
  8. If ar[mid] > n, the target is in the left half, so set end = mid - 1.
main.c 
#include<stdio.h>
int main() {
 int beg, end, mid, n;
 int ar[9]={1,2,3,4,5,6,7,8,9};
 printf("Enter no. to Search:");
 scanf("%d", &n);
 beg = 0;
 end = 8;
 while (beg < = end) {
  mid = (beg+end)/2;	
  if(ar[mid] == n) {
   printf("Found at %d pos\n",mid);
   break;
  }
  else if(ar[mid] < n) {
   beg = mid + 1;
  }
  else {
   end = mid - 1;
  }
 }
 if (beg > end)
  printf("Not found!");
 return 0;   
}

Expected Output

OUTPUT : 1
Enter no. to Search: 8
Found at 7 pos.

OUTPUT : 2
Enter no. to Search: 17
Not found.

Explanation of the Program

  • Binary Search is drastically faster than Linear Search, but it ONLY works on arrays that are already sorted.
  • It works like searching for a word in a dictionary. You open it to the exact middle. If the word you are looking for comes alphabetically after the middle page, you completely ignore the entire left half of the dictionary, cutting your search space in half instantly.

Complexity

Time Complexity O(log n) - Search space is halved every iteration.
Space Complexity O(1)
ADVERTISEMENT