Binary Search DC
Binary search is a classic divide-and-conquer algorithm for finding an element in a sorted array. It repeatedly divides the search interval in half. Time O(log n). The recursive version demonstrates the divide-and-conquer pattern.
Recursive implementation:
public static int binarySearch(int[] arr, int target, int left, int right) {
if (left > right) return -1;
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) return binarySearch(arr, target, mid + 1, right);
else return binarySearch(arr, target, left, mid - 1);
}
Divide step: compute mid. Conquer: recursively search left or right half. Combine step is trivial (return result). The iterative version is often preferred for space efficiency, but the recursive form illustrates the divide-and-conquer structure.
Two Minute Drill
- Binary search finds element in sorted array in O(log n).
- Divide by half at each step.
- Recursive version: base case when left > right.
- Used in many algorithms and data structures.
Need more clarification?
Drop us an email at career@quipoinfotech.com