Problem Statement
What is the prerequisite for applying binary search on an array?
Explanation
Binary search requires the array to be sorted because the algorithm relies on comparing the middle element with the target to decide which half to search next. If the array is not sorted, this comparison does not provide meaningful information about where the target might be.
The algorithm works by repeatedly dividing the search space in half. If the middle element is greater than the target, we search the left half. If it is less, we search the right half. This only works when elements are in sorted order. The array does not need unique elements, a specific size, or any particular memory layout.
Code Solution
SolutionRead Only
// Binary Search - Requires sorted array
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; // Search right half
else
right = mid - 1; // Search left half
}
return -1; // Not found
}
// Example: [1, 3, 5, 7, 9, 11, 13]
// Search 7:
// Step 1: mid=3, arr[3]=7, found!
// Time: O(log n)