Binary Search
Binary search is an efficient algorithm for finding an element in a sorted array. It repeatedly divides the search interval in half. If the target is less than the middle, it searches the left half; otherwise, the right half. Time complexity: O(log n).
Java implementation (iterative):
public static 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;
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
Binary search requires the array to be sorted. It's the foundation for many other algorithms.
Two Minute Drill
- Binary search works on sorted arrays.
- Time O(log n), space O(1) (iterative) or O(log n) recursive.
- Efficient for large data.
- Used in many problems like find first/last occurrence.
Need more clarification?
Drop us an email at career@quipoinfotech.com