Your Progress
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:
- If the target value equals the middle element, the search is successful.
- If the target value is less than the middle element, search the left half of the array.
- If the target value is greater than the middle element, search the right half of the array.
- 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>23// Iterative Binary Search4int binarySearch(int arr[], int n, int target) {5 int left = 0;6 int right = n - 1;78 while (left <= right) {9 int mid = left + (right - left) / 2;1011 // Check if target is present at mid12 if (arr[mid] == target)13 return mid;1415 // If target is greater, ignore left half16 if (arr[mid] < target)17 left = mid + 1;1819 // If target is smaller, ignore right half20 else21 right = mid - 1;22 }2324 // Element not present in array25 return -1;26}2728// Recursive Binary Search29int binarySearchRecursive(int arr[], int left, int right, int target) {30 if (right >= left) {31 int mid = left + (right - left) / 2;3233 // If the element is present at the middle34 if (arr[mid] == target)35 return mid;3637 // If element is smaller than mid, search in left subarray38 if (arr[mid] > target)39 return binarySearchRecursive(arr, left, mid - 1, target);4041 // Else search in right subarray42 return binarySearchRecursive(arr, mid + 1, right, target);43 }4445 // Element not present in array46 return -1;47}4849int main() {50 int arr[] = {2, 3, 4, 10, 40, 50, 70, 85};51 int n = sizeof(arr) / sizeof(arr[0]);52 int target = 10;5354 int result = binarySearch(arr, n, target);55 if (result == -1)56 printf("Element %d not present in array\n", target);57 else58 printf("Element %d found at index %d\n", target, result);5960 result = binarySearchRecursive(arr, 0, n - 1, target);61 if (result == -1)62 printf("Element %d not present in array (recursive)\n", target);63 else64 printf("Element %d found at index %d (recursive)\n", target, result);6566 return 0;67}
Time and Space Complexity
Complexity | Best Case | Average Case | Worst Case |
---|---|---|---|
Time Complexity | O(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:
- Linear Search - Simple search algorithm with O(n) time complexity
- Depth-First Search - Graph traversal algorithm that explores as far as possible along each branch
- Breadth-First Search - Graph traversal algorithm that explores all neighbors at the present depth
- Interpolation Search - Improved variant of binary search for uniformly distributed data
Related Tutorials
Linear Search
Learn how to implement the linear search algorithm.
Learn moreDepth-First Search
Learn how to implement the depth-first search algorithm for graphs.
Learn moreBreadth-First Search
Learn how to implement the breadth-first search algorithm for graphs.
Learn more