Algorithm & C Program for Binary Search
Subject: PPS (Programming for Problem Solving)
Contributed By: Sanjay
Created At: February 3, 2025
Question:
Exaplain in detail about Binary Search With an Example and Program.
Explanation Video:
Explanation:
Binary Search Procedure
Binary search is an efficient searching algorithm that works on a sorted array. It follows the divide and conquer approach by repeatedly dividing the search space in half until the target element is found.
Steps of Binary Search:
Sort the array (if not already sorted).
Initialize two pointers: low (start of the array) and high (end of the array).
Find the middle element (mid) using the formula: mid=low+high2mid = \frac{low + high}{2}
Compare arr[mid] with the search key:
If arr[mid] == key, the element is found, and the search stops.
If arr[mid] > key, search in the left half (high = mid - 1).
If arr[mid] < key, search in the right half (low = mid + 1).
Repeat steps 3-4 until low exceeds high (element is not found).
Dry Run of Binary Search
Given Sorted Array:
arr = [10, 20, 30, 40, 50]
Search key = 30
Step-by-Step Execution:
Initial values: low = 0, high = 4
Calculate mid = (0 + 4) / 2 = 2
arr[mid] = 30, which matches the key → Element found at index 2
Search stops.
Dry Run for Unsuccessful Search (Key = 35)
Initial values: low = 0, high = 4
Calculate mid = (0 + 4) / 2 = 2
arr[mid] = 30, but 30 < 35, so search the right half (low = mid + 1 = 3)
New values: low = 3, high = 4
Calculate mid = (3 + 4) / 2 = 3
arr[mid] = 40, but 40 > 35, so search the left half (high = mid - 1 = 2)
Now low (3) > high (2), so element is not found.
Final Result:
- If the key is 30, found at index 2.
- If the key is 35, not found in the array.
Binary search is much faster than linear search, especially for large datasets, as it eliminates half of the search space in each step.
#include <stdio.h>
int binarySearch(int arr[], int left, int right, int key) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == key)
return mid;
else if (arr[mid] < key)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
int main() {
int arr[] = {10, 20, 30, 40, 50};
int key = 40;
int n = sizeof(arr) / sizeof(arr[0]);
int result = binarySearch(arr, 0, n - 1, key);
if (result != -1)
printf("Element found at index %d\n", result);
else
printf("Element not found\n");
return 0;
}
Element found at index 3