Binary Search | CrackEase

Binary Search

Binary search is an efficient search algorithm that works on sorted arrays (ascending or descending). It repeatedly divides the search interval in half: compare the key with the middle element, and decide whether to continue in the left half or the right half.

Implementation

Step 1 — Ensure the array is sorted.

Step 2 — Compute mid using mid = left + (right - left) / 2 (avoids overflow).

Step 3 — If arr[mid] == item return mid.

Step 4 — If arr[mid] < item, search the right subarray (mid+1..right); otherwise search the left subarray (left..mid-1).

Step 5 — Repeat until bounds cross; if not found, return -1.

Methods Discussed

We cover two common implementations:

Recursive approach
Iterative approach

Binary Search (Recursive Approach)

  
// Binary Search implementation in C (Recursive)
// Time Complexity : O(log n)
// Space Complexity : O(1) (excluding recursion stack)
// Auxiliary Space (recursion) : O(log n)

#include <stdio.h>

int binarySearch(int arr[], int left, int right, int item) {
    if (right < left) return -1;

    int mid = left + (right - left) / 2;

    if (arr[mid] == item)
        return mid;
    else if (arr[mid] > item)
        return binarySearch(arr, left, mid - 1, item);
    else
        return binarySearch(arr, mid + 1, right, item);
}

int main() {
    int arr[] = {10, 20, 30, 40, 50, 60, 70, 80};
    int n = sizeof(arr) / sizeof(arr[0]);
    int item = 70;

    int position = binarySearch(arr, 0, n - 1, item);

    if (position == -1)
        printf("%d Not Found", item);
    else
        printf("%d Found at index : %d", item, position);

    return 0;
}

  
// Binary Search implementation in C++ (Recursive)
// Time Complexity : O(log n)
// Auxiliary Space (recursion) : O(log n)

#include <bits/stdc++.h>
using namespace std;

int binarySearch(int array[], int left, int right, int item) {
    if (right < left) return -1;

    int mid = left + (right - left) / 2;

    if (array[mid] == item)
        return mid;
    else if (array[mid] > item)
        return binarySearch(array, left, mid - 1, item);
    else
        return binarySearch(array, mid + 1, right, item);
}

int main() {
    int array[] = {10, 20, 30, 40, 50, 60, 70, 80}; // sorted
    int n = sizeof(array) / sizeof(array[0]);
    int item = 70;

    int position = binarySearch(array, 0, n - 1, item);

    if (position == -1)
        cout << item << " Not Found";
    else
        cout << item << " Found at index : " << position;

    return 0;
}

  
// Binary Search implementation in Java (Recursive)
// Time Complexity : O(log n)
// Auxiliary Space (recursion) : O(log n)

public class Main {

    public static int binarySearch(int array[], int left, int right, int item) {
        if (right < left) return -1;

        int mid = left + (right - left) / 2;

        if (array[mid] == item)
            return mid;
        else if (array[mid] > item)
            return binarySearch(array, left, mid - 1, item);
        else
            return binarySearch(array, mid + 1, right, item);
    }

    public static void main(String args[]) {
        int[] array = {10, 20, 30, 40, 50, 60, 70, 80};
        int item = 70;
        int size = array.length;

        int position = binarySearch(array, 0, size - 1, item);

        if (position == -1)
            System.out.println("Element not found");
        else
            System.out.println(item + " found at index: " + position);
    }
}

	
70 Found at index : 6

Binary Search in C (Iterative Approach)

  
// Binary Search implementation in C (Iterative)
// Time Complexity : O(log n)
// Space Complexity : O(1)

#include <stdio.h>

int binarySearch(int arr[], int l, int r, int item) {
    while (l <= r) {
        int mid = l + (r - l) / 2;

        if (arr[mid] == item)
            return mid;
        else if (arr[mid] < item)
            l = mid + 1;
        else
            r = mid - 1;
    }
    return -1;
}

int main(void) {
    int arr[] = {10, 20, 30, 40, 50, 60, 70, 80};
    int n = sizeof(arr) / sizeof(arr[0]);
    int item = 30;

    int position = binarySearch(arr, 0, n - 1, item);

    if (position == -1)
        printf("%d Not Found", item);
    else
        printf("%d Found at index : %d", item, position);

    return 0;
}

  
// Binary Search implementation in C++ (Iterative)
// Time Complexity : O(log n)
// Space Complexity : O(1)

#include <bits/stdc++.h>
using namespace std;

int binarySearch(int arr[], int l, int r, int item) {
    while (l <= r) {
        int mid = l + (r - l) / 2;

        if (arr[mid] == item)
            return mid;
        else if (arr[mid] < item)
            l = mid + 1;
        else
            r = mid - 1;
    }
    return -1;
}

int main() {
    int arr[] = {10, 20, 30, 40, 50, 60, 70, 80};
    int n = sizeof(arr) / sizeof(arr[0]);
    int item = 30;

    int position = binarySearch(arr, 0, n - 1, item);

    if (position == -1)
        cout << item << " Not Found";
    else
        cout << item << " Found at index : " << position;

    return 0;
}

  
// Binary Search implementation in Java (Iterative)
// Time Complexity : O(log n)
// Space Complexity : O(1)

public class Main {
    public static int binarySearch(int array[], int left, int right, int item) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (array[mid] == item) return mid;
            else if (array[mid] < item) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }

    public static void main(String args[]) {
        int[] array = {10, 20, 30, 40, 50, 60, 70, 80};
        int item = 30;
        int position = binarySearch(array, 0, array.length - 1, item);

        if (position == -1)
            System.out.println("Element not found");
        else
            System.out.println(item + " found at index : " + position);
    }
}

	
30 Found at index : 2

Time Complexity for Binary Search

Best	Average	Worst	Space Complexity	Average Comparisons
O(1)	O(log n)	O(log n)	O(1)	≈ log₂(n)

Footer Content | CrackEase

→

←

Courses

Chapters

Data Structure

Sorting

Linked List

Stack

Queue

Tree

Binary Search

Binary Search