Binary Search in Java: Theory and Applications
In-depth exploration of binary search algorithm in Java, including iterative and recursive implementations, and its applications in problem-solving.
Binary Search Practice Problems and Solutions in Java
This page provides a series of practice problems on binary search in Java, along with detailed solutions and explanations. The goal is to reinforce your understanding of binary search and its applications in competitive programming.
Practice Problems
Problem 1: Find the element in a sorted array
Given a sorted array of integers, find the index of a given target element. If the element is not present, return -1.
Solution
public class BinarySearch {
public static int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // Prevents potential overflow
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // Target not found
}
public static void main(String[] args) {
int[] arr = {2, 5, 7, 8, 11, 12};
int target = 13;
int index = binarySearch(arr, target);
if (index == -1) {
System.out.println("Element not found");
} else {
System.out.println("Element found at index: " + index);
}
}
}Explanation
This solution implements the standard binary search algorithm. It initializes `left` and `right` pointers to the beginning and end of the array, respectively. The `while` loop continues as long as `left` is less than or equal to `right`. Inside the loop, it calculates the middle index `mid`. If the element at `mid` is equal to the target, the index `mid` is returned. If the element at `mid` is less than the target, the search continues in the right half of the array by updating `left` to `mid + 1`. Otherwise, the search continues in the left half of the array by updating `right` to `mid - 1`. If the target is not found after the loop completes, -1 is returned.
The calculation of `mid` as `left + (right - left) / 2` prevents potential integer overflow that could occur if `left + right` exceeds the maximum value of an `int`.
Problem 2: Find the first occurrence of an element in a sorted array
Given a sorted array of integers that may contain duplicate elements, find the index of the first occurrence of a given target element. If the element is not present, return -1.
Solution
public class FirstOccurrence {
public static int findFirstOccurrence(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
int result = -1; // Initialize result to -1
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
result = mid; // Found an occurrence, but keep searching left
right = mid - 1;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
public static void main(String[] args) {
int[] arr = {2, 5, 7, 7, 7, 8, 8, 11, 12};
int target = 7;
int index = findFirstOccurrence(arr, target);
if (index == -1) {
System.out.println("Element not found");
} else {
System.out.println("First occurrence found at index: " + index);
}
}
}Explanation
This solution modifies the standard binary search to find the *first* occurrence of the target element. When the target element is found at `arr[mid]`, the `result` is updated to `mid`. Crucially, instead of returning immediately, the `right` pointer is moved to `mid - 1` to continue searching for the target in the left half of the array. This ensures that we eventually find the leftmost (first) occurrence. If the target is not found, the initial value of `result` (-1) is returned.
Problem 3: Find the last occurrence of an element in a sorted array
Given a sorted array of integers that may contain duplicate elements, find the index of the last occurrence of a given target element. If the element is not present, return -1.
Solution
public class LastOccurrence {
public static int findLastOccurrence(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
int result = -1; // Initialize result to -1
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
result = mid; // Found an occurrence, but keep searching right
left = mid + 1;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
public static void main(String[] args) {
int[] arr = {2, 5, 7, 7, 7, 8, 8, 11, 12};
int target = 7;
int index = findLastOccurrence(arr, target);
if (index == -1) {
System.out.println("Element not found");
} else {
System.out.println("Last occurrence found at index: " + index);
}
}
}Explanation
This solution is similar to finding the first occurrence, but it modifies the binary search to find the *last* occurrence. When the target element is found at `arr[mid]`, the `result` is updated to `mid`, but instead of returning, the `left` pointer is moved to `mid + 1` to continue searching for the target in the right half of the array. This ensures that we eventually find the rightmost (last) occurrence. If the target is not found, the initial value of `result` (-1) is returned.
Problem 4: Find the element in a rotated sorted array (no duplicates)
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). You are given a target value to search. If found in the array return its index, otherwise return -1. You may assume no duplicate exists in the array.
Solution
public class RotatedArraySearch {
public static int searchRotatedArray(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
}
// Check if left half is sorted
if (nums[left] <= nums[mid]) {
if (target >= nums[left] && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
// Right half is sorted
else {
if (target > nums[mid] && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1; // Target not found
}
public static void main(String[] args) {
int[] nums = {4, 5, 6, 7, 0, 1, 2};
int target = 0;
int index = searchRotatedArray(nums, target);
if (index == -1) {
System.out.println("Element not found");
} else {
System.out.println("Element found at index: " + index);
}
}
}Explanation
This solution adapts binary search to work on a rotated sorted array. The key idea is to determine which half of the array (left or right) is sorted. If the left half is sorted (nums[left] <= nums[mid]), we check if the target lies within the sorted left half (target >= nums[left] && target < nums[mid]). If it does, we search in the left half (right = mid - 1). Otherwise, we search in the right half (left = mid + 1). If the left half is not sorted, it means the right half is sorted. We then check if the target lies within the sorted right half (target > nums[mid] && target <= nums[right]) and search accordingly. This process continues until the target is found or the search space is exhausted.
Problem 5: Find the peak element
A peak element is an element that is greater than its neighbors. Given an input array where nums[i] != nums[i+1], find a peak element and return its index. The array may contain multiple peaks, in that case return the index to any one of the peaks. You may imagine that nums[-1] = nums[n] = -∞.
Solution
public class PeakElement {
public static int findPeakElement(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[mid + 1]) {
right = mid; // Peak is to the left or at mid
} else {
left = mid + 1; // Peak is to the right
}
}
return left; // left and right converge to the peak element
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 1};
int peakIndex = findPeakElement(nums);
System.out.println("Peak element index: " + peakIndex);
}
}Explanation
This solution uses binary search to efficiently find a peak element. The key observation is that if nums[mid] > nums[mid + 1], then a peak element must exist in the range [left, mid] (inclusive), because either mid is a peak, or a peak exists somewhere to its left. Therefore, we can safely update right = mid. Conversely, if nums[mid] < nums[mid + 1], then a peak element must exist in the range [mid + 1, right] (inclusive), because a peak exists somewhere to the right of mid. We update left = mid + 1. The loop continues until left and right converge to the same index, which represents the index of a peak element.