WikiGalaxy
Binary Search Basics
Introduction to Binary Search
Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing the portion of the list that could contain the item in half until you've narrowed down the possible locations to just one.
// Java implementation of binary search
class BinarySearch {
int binarySearch(int arr[], int l, int r, int x) {
if (r >= l) {
int mid = l + (r - l) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
return binarySearch(arr, mid + 1, r, x);
}
return -1;
}
}
Console Output:
Element found at index 3
Iterative Binary Search
Iterative Approach
Unlike the recursive approach, the iterative method uses a loop to divide the search space in half. This method is often preferred in languages without tail recursion optimization.
// Iterative binary search in Java
class IterativeBinarySearch {
int binarySearch(int arr[], int x) {
int l = 0, r = arr.length - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] < x)
l = mid + 1;
else
r = mid - 1;
}
return -1;
}
}
Console Output:
Element found at index 5
Binary Search on a 2D Array
Searching in 2D Matrices
Binary search can also be applied to 2D arrays, particularly when each row and column is sorted. This allows for efficient searching with a time complexity of O(log(m*n)).
// Binary search in a 2D array
class MatrixBinarySearch {
boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0) return false;
int m = matrix.length, n = matrix[0].length;
int left = 0, right = m * n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
int midVal = matrix[mid / n][mid % n];
if (midVal == target) return true;
if (midVal < target) left = mid + 1;
else right = mid - 1;
}
return false;
}
}
Console Output:
Element found: true
Binary Search for First Occurrence
Finding First Occurrence
Sometimes, you need to find the first occurrence of an element in a sorted array. This can be achieved by modifying the binary search algorithm to continue searching even after finding a match.
// Binary search for first occurrence
class FirstOccurrenceBinarySearch {
int firstOccurrence(int arr[], int x) {
int l = 0, r = arr.length - 1, result = -1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (arr[mid] == x) {
result = mid;
r = mid - 1;
} else if (arr[mid] < x) {
l = mid + 1;
} else {
r = mid - 1;
}
}
return result;
}
}
Console Output:
First occurrence at index 2
Binary Search for Last Occurrence
Finding Last Occurrence
Similarly, to find the last occurrence of an element, adjust the binary search to continue searching on the right side after finding a match.
// Binary search for last occurrence
class LastOccurrenceBinarySearch {
int lastOccurrence(int arr[], int x) {
int l = 0, r = arr.length - 1, result = -1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (arr[mid] == x) {
result = mid;
l = mid + 1;
} else if (arr[mid] < x) {
l = mid + 1;
} else {
r = mid - 1;
}
}
return result;
}
}
Console Output:
Last occurrence at index 4
