Your Progress

7/30 completed

23% complete. Continue learning to master DSA!

Binary Search Algorithm

Binary Search is an efficient algorithm for finding an element in a sorted array. It works by repeatedly dividing the search interval in half, making it much faster than linear search for large datasets.

💡 Key Takeaways

  • Binary Search requires a sorted array to work correctly
  • It has O(log n) time complexity, making it very efficient for large datasets
  • It uses a divide-and-conquer approach to eliminate half of the remaining elements in each step
  • Binary Search can be implemented iteratively or recursively

How Binary Search Works

Binary Search works by comparing the target value to the middle element of the array:

  1. If the target value equals the middle element, the search is successful.
  2. If the target value is less than the middle element, search the left half of the array.
  3. If the target value is greater than the middle element, search the right half of the array.
  4. Repeat this process until the value is found or the search interval is empty.

Visual Representation

Visualization of Binary Search algorithm in action

Binary Search Animation Placeholder

Binary Search Implementation

Below are implementations of the Binary Search algorithm in multiple programming languages:

1#include <stdio.h>
2
3// Iterative Binary Search
4int binarySearch(int arr[], int n, int target) {
5 int left = 0;
6 int right = n - 1;
7
8 while (left <= right) {
9 int mid = left + (right - left) / 2;
10
11 // Check if target is present at mid
12 if (arr[mid] == target)
13 return mid;
14
15 // If target is greater, ignore left half
16 if (arr[mid] < target)
17 left = mid + 1;
18
19 // If target is smaller, ignore right half
20 else
21 right = mid - 1;
22 }
23
24 // Element not present in array
25 return -1;
26}
27
28// Recursive Binary Search
29int binarySearchRecursive(int arr[], int left, int right, int target) {
30 if (right >= left) {
31 int mid = left + (right - left) / 2;
32
33 // If the element is present at the middle
34 if (arr[mid] == target)
35 return mid;
36
37 // If element is smaller than mid, search in left subarray
38 if (arr[mid] > target)
39 return binarySearchRecursive(arr, left, mid - 1, target);
40
41 // Else search in right subarray
42 return binarySearchRecursive(arr, mid + 1, right, target);
43 }
44
45 // Element not present in array
46 return -1;
47}
48
49int main() {
50 int arr[] = {2, 3, 4, 10, 40, 50, 70, 85};
51 int n = sizeof(arr) / sizeof(arr[0]);
52 int target = 10;
53
54 int result = binarySearch(arr, n, target);
55 if (result == -1)
56 printf("Element %d not present in array\n", target);
57 else
58 printf("Element %d found at index %d\n", target, result);
59
60 result = binarySearchRecursive(arr, 0, n - 1, target);
61 if (result == -1)
62 printf("Element %d not present in array (recursive)\n", target);
63 else
64 printf("Element %d found at index %d (recursive)\n", target, result);
65
66 return 0;
67}

Time and Space Complexity

ComplexityBest CaseAverage CaseWorst Case
Time ComplexityO(1)O(log n)O(log n)
Space Complexity (Iterative)O(1)O(1)O(1)
Space Complexity (Recursive)O(1)O(log n)O(log n)

Time Complexity Analysis

  • Best Case: O(1) when the target element is at the middle of the array and found in the first comparison.
  • Average Case: O(log n) as we eliminate half of the remaining elements in each step.
  • Worst Case: O(log n) even when the element is not in the array or is at the beginning/end.

Space Complexity Analysis

The iterative implementation of Binary Search has a space complexity of O(1) as it only uses a constant amount of extra space. The recursive implementation has a space complexity of O(log n) due to the call stack.

Advantages and Disadvantages

Advantages

  • Much faster than linear search for large datasets
  • O(log n) time complexity makes it very efficient
  • Works well with arrays that are already sorted
  • Predictable performance regardless of data distribution
  • Iterative implementation uses constant space

Disadvantages

  • Requires a sorted array to work correctly
  • Sorting an unsorted array first adds additional time complexity
  • Not efficient for small datasets compared to linear search
  • Only works with data structures that allow random access (like arrays)
  • Not suitable for linked lists or other sequential access data structures

Common Applications

Binary Search is used in many real-world applications:

  • Database Systems: For searching through sorted indices.
  • Dictionary Lookups: Finding words in a sorted dictionary.
  • Debugging: Binary search debugging (bisect) to find bugs in code.
  • Computer Graphics: For intersection detection in ray tracing.
  • Machine Learning: In algorithms like binary decision trees.

Variations of Binary Search

Several variations of the Binary Search algorithm exist for different scenarios:

Lower Bound Binary Search

Finds the first occurrence of an element in a sorted array with duplicates.

Upper Bound Binary Search

Finds the last occurrence of an element in a sorted array with duplicates.

Binary Search on Answer

Used to find the optimal value that satisfies certain conditions, often in optimization problems.

Practice Problems

To solidify your understanding of Binary Search, try these practice problems:

Problem 1: First and Last Position

Find the first and last position of a given element in a sorted array with duplicates.

Problem 2: Search in Rotated Sorted Array

Implement a binary search in a sorted array that has been rotated at some pivot.

Problem 3: Square Root Using Binary Search

Implement a function to find the square root of a number using binary search.

Related Searching Algorithms

If you're interested in learning more about searching algorithms, here are some related algorithms to explore:

Related Tutorials

Linear Search

Learn how to implement the linear search algorithm.

Learn more

Depth-First Search

Learn how to implement the depth-first search algorithm for graphs.

Learn more

Breadth-First Search

Learn how to implement the breadth-first search algorithm for graphs.

Learn more