Data Structures and Algorithms Tutorials | IT Developer
IT Developer

Data Structures & Algorithms - Binary Search Algorithm

Share with a Friend
Previous
HOME
Next

Binary Search Algorithm

Binary Search is an efficient algorithm for finding a target element in a sorted array. It works by repeatedly dividing the search interval in half.

📌 Key Requirements

  • The array must be sorted.
  • Works on divide-and-conquer principle.

🔁 How Binary Search Works?

  1. Find the middle element.
  2. Compare it with the target:
    • If equal: target found.
    • If target < middle: search in the left half.
    • If target > middle: search in the right half.
  3. Repeat until found or interval becomes empty.

⏱ Time Complexity

Case Time
Best Case

O(1)
Average

O(log n)
Worst Case

O(log n)

🧠 Space Complexity

  • Iterative version: O(1)
  • Recursive version: O(log n) due to call stack

📋 Pseudocode

 

function binarySearch(array, target):


    left = 0


    right = length(array) - 1

 
    while left <= right:


        mid = (left + right) // 2


        if array[mid] == target:


            return mid


        else if array[mid] < target:


            left = mid + 1


        else:


            right = mid - 1


    return -1

Detailed Explanation & Example: Binary Search

Algorithm:

  1. Find the middle element of the array.
  2. If middle element is equal to target, return index.
  3. If target is less, repeat search in left subarray.
  4. If target is greater, repeat search in right subarray.
  5. If subarray size reduces to zero, target is not found.

Binary Search implementation - C, C++, Java, Python

C C++ Java Python 
#include <stdio.h>


 


int binarySearch(int arr[], int n, int target) {


    int left = 0, right = n -1;


    while (left <= right) {


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


        if (arr[mid] == target) return mid;


        else if (arr[mid] < target) left = mid + 1;


        else right = mid - 1;


    }


    return -1;


}


 


int main() {


    int arr[] = {10, 20, 30, 40, 50};


    int n = sizeof(arr)/sizeof(arr[0]);


    int target = 30;


    int result = binarySearch(arr, n, target);


    if (result != -1)


        printf("Element found at index %d\n", result);


    else


        printf("Element not found\n");


    return 0;


}

Output

Element found at index 2


#include <iostream>


using namespace std;


 


int binarySearch(int arr[], int n, int target) {


    int left = 0, right = n - 1;


    while (left <= right) {


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


        if (arr[mid] == target) return mid;


        else if (arr[mid] < target) left = mid + 1;


        else right = mid - 1;


    }


    return -1;


}


 


int main() {


    int arr[] = {10, 20, 30, 40, 50};


    int n = sizeof(arr)/sizeof(arr[0]);


    int target = 30;


    int result = binarySearch(arr, n, target);


    if (result != -1)


        cout << "Element found at index " << result << endl;


    else


        cout << "Element not found" << endl;


    return 0;


}

Output

Element found at index 2


public class BinarySearch {


    public static int binarySearch(int[] arr, int target) {


        int left = 0, right = arr.length - 1;


        while (left <= right) {


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


            if (arr[mid] == target)


                return mid;


            if (arr[mid] < target)


                left = mid + 1;


            else


                right = mid - 1;


        }


        return -1;


    }


    public static void main(String[] args) {


        int[] arr = {10, 20, 30, 40, 50};


        int target = 30;


        int result = binarySearch(arr, target);


        if (result != -1)


            System.out.println("Element found at index " + result);


        else


            System.out.println("Element not found");


    }


}

Output

Element found at index 2


def binary_search(arr, target):


    left, right = 0, len(arr) -1


    while left <= right:


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


        if arr[mid] == target:


            return mid


        elif arr[mid] < target:


            left = mid + 1


        else:


            right = mid - 1


    return -1


 


arr = [10, 20, 30, 40, 50]


target = 30


result = binary_search(arr, target)


if result != -1:


    print(f"Element found at index {result}")


else:


    print("Element not found")

Output

Element found at index 2

📌 Real-World Applications of Binary Search

  • Finding a word in a dictionary app.
  • Looking up entries in phone books.
  • Search in sorted databases.
  • Used in libraries like bisect in Python and Java’s binarySearch().

 

Previous
Next