🔴 Advanced · Lesson 41

Binary Search

Binary search is a fast searching algorithm for a sorted array. It repeatedly divides the search range into half.

Condition

The array must be sorted before applying binary search.

Algorithm

Set low = 0 and high = n-1
Find mid = (low + high) / 2
If arr[mid] == key, search successful
If key is smaller, search left half
If key is larger, search right half

Iterative Program

C Language

#include <stdio.h>

int binarySearch(int arr[], int n, int key) {
    int low = 0, high = n - 1;
    while(low <= high) {
        int mid = low + (high - low) / 2;
        if(arr[mid] == key) return mid;
        else if(key < arr[mid]) high = mid - 1;
        else low = mid + 1;
    }
    return -1;
}

int main() {
    int arr[] = {10, 20, 30, 40, 50, 60};
    int key = 40;
    int pos = binarySearch(arr, 6, key);
    if(pos == -1) printf("Not found");
    else printf("Found at index %d", pos);
    return 0;
}

Found at index 3

Recursive Program

C Language

int binaryRecursive(int arr[], int low, int high, int key) {
    if(low > high) return -1;
    int mid = low + (high - low) / 2;
    if(arr[mid] == key) return mid;
    if(key < arr[mid]) return binaryRecursive(arr, low, mid - 1, key);
    return binaryRecursive(arr, mid + 1, high, key);
}

Summary

Binary search works only on sorted data
Time complexity is O(log n)
It is faster than linear search for large arrays
Use safe mid formula: low + (high-low)/2
Can be implemented iteratively or recursively

Binary Search

Binary search sorted array में fast searching algorithm है। यह हर step पर search range को आधा कर देता है।

Condition

Binary search लगाने से पहले array sorted होना चाहिए।

Algorithm

low = 0 और high = n-1 रखें
mid निकालें
arr[mid] key के बराबर है तो found
key छोटा है तो left half
key बड़ा है तो right half

Iterative Program

C Language

int binarySearch(int arr[], int n, int key) {
    int low = 0, high = n - 1;
    while(low <= high) {
        int mid = low + (high - low) / 2;
        if(arr[mid] == key) return mid;
        else if(key < arr[mid]) high = mid - 1;
        else low = mid + 1;
    }
    return -1;
}

Recursive Program

C Language

int bs(int a[], int low, int high, int key) {
    if(low > high) return -1;
    int mid = low + (high - low) / 2;
    if(a[mid] == key) return mid;
    if(key < a[mid]) return bs(a, low, mid-1, key);
    return bs(a, mid+1, high, key);
}

सारांश

Binary search sorted data पर काम करता है
Time complexity O(log n) है
Large arrays में linear search से तेज है
Safe mid formula use करें
Iterative और recursive दोनों तरीके हैं

← Back to C Tutorial