Binary Search (Divide & Conquer)
Efficiently search in sorted arrays using the divide and conquer paradigm
Binary Search (Divide & Conquer)
Binary Search is a highly efficient search algorithm that repeatedly divides the search interval in half, comparing the target with the middle element.
Theory & Concepts
Definition:
Binary Search works on sorted arrays by comparing the target value with the middle element and eliminating half of the search space in each iteration.
Key Points:
- Requires sorted array as prerequisite
- O(log n) time complexity - very efficient
- Uses divide and conquer paradigm
- Eliminates half of search space in each step
Applications:
- Searching in databases with indexed data
- Finding elements in sorted collections
- Root finding in numerical methods
- Searching in game trees and decision trees
University Guidelines
Exam Weightage
4-6 marks MarksSyllabus Coverage:
- Binary search algorithm implementation
- Divide and conquer approach
- Recurrence relation: T(n) = T(n/2) + O(1)
- Iterative vs recursive implementation
- Best, average and worst case analysis
Common Questions:
- Implement binary search algorithm
- Trace binary search execution
- Analyze time complexity using recurrence
- Compare with linear search
Exam Tips:
Always mention sorted array prerequisite
Show step-by-step search process
Calculate mid using (left + right) / 2
Handle base cases properly
Algorithm Details
O(log n) - all cases
Time Complexity
O(1) iterative, O(log n) recursive
Space Complexity
Algorithm Steps:
- 1Initialize left = 0, right = array.length - 1
- 2Calculate mid = (left + right) / 2
- 3Compare target with array[mid]
- 4If equal, return mid; if target < array[mid], search left half
- 5If target > array[mid], search right half
- 6Repeat until found or left > right
Configure Binary Search
💡 Enter numbers separated by commas. They will be automatically sorted.
✓Sorted Array (10 elements):
1[0]
3[1]
5[2]
7[3]
9[4]
11[5]
13[6]
15[7]
17[8]
19[9]
Target: 7
Search Results
🔍
Click "Search" to start the binary search visualization
Why Binary Search is O(log n)
Search Space Reduction
Initial size: n elements
After 1 comparison: n/2 elements
After 2 comparisons: n/4 elements
After 3 comparisons: n/8 elements
After k comparisons: n/2^k elements
Maximum k = log₂(n)
Comparison with Linear Search
Linear Search: O(n) - checks each element
Binary Search: O(log n) - eliminates half each time
For 1000 elements:
• Linear: up to 1000 comparisons
• Binary: up to 10 comparisons