Binary Search: A Comprehensive Guide
Binary Search is an efficient algorithm for searching a sorted array by repeatedly dividing the search interval in half. It follows the divide-and-conquer approach and has a time complexity of O(log n), making it much faster than linear search for large datasets.
How Binary Search Works
- The algorithm starts with the middle element of the sorted array.
- If the target value is equal to the middle element, the search is complete.
- If the target value is less than the middle element, the search continues in the lower half of the array.
- If the target value is greater than the middle element, the search continues in the upper half of the array.
- This process is repeated until the target value is found or it is clear that the target is not in the array.
Implementation in Java
Here's a basic implementation of Binary Search in Java:
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;
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, 3, 4, 10, 40};
int target = 10;
int result = binarySearch(arr, target);
if (result == -1) {
System.out.println("Element not present");
} else {
System.out.println("Element found at index " + result);
}
}
}
Implementation in C++
Here's the same implementation in C++:
#include <iostream>
#include <vector>
class BinarySearch {
public:
static int binarySearch(std::vector<int>& arr, int target) {
int left = 0;
int right = arr.size() - 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; // Target not found
}
};
int main() {
std::vector<int> arr = {2, 3, 4, 10, 40};
int target = 10;
int result = BinarySearch::binarySearch(arr, target);
if (result == -1) {
std::cout << "Element not present" << std::endl;
} else {
std::cout << "Element found at index " << result << std::endl;
}
return 0;
}
Popular Interview Problems
Let's look at some popular interview problems related to Binary Search and their solutions in both Java and C++.
1. Find First and Last Position of Element in Sorted Array
Problem: Given a sorted array of integers and a target value, find the starting and ending position of the target value in the array. If the target is not found, return [-1, -1].
Java Solution:
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] result = {-1, -1};
result[0] = findFirstPosition(nums, target);
result[1] = findLastPosition(nums, target);
return result;
}
private int findFirstPosition(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
if (mid == left || nums[mid - 1] < target) {
return mid;
}
right = mid - 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
private int findLastPosition(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
if (mid == right || nums[mid + 1] > target) {
return mid;
}
left = mid + 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
}
C++ Solution:
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
vector<int> result(2, -1);
result[0] = findFirstPosition(nums, target);
result[1] = findLastPosition(nums, target);
return result;
}
private:
int findFirstPosition(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
if (mid == left || nums[mid - 1] < target) {
return mid;
}
right = mid - 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
int findLastPosition(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
if (mid == right || nums[mid + 1] > target) {
return mid;
}
left = mid + 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
};
Explanation: This problem uses two separate binary searches to find the first and last positions of the target value. The findFirstPosition function looks for the leftmost occurrence, while findLastPosition looks for the rightmost occurrence.
2. Search in Rotated Sorted Array
Problem: Given a rotated sorted array and a target value, return the index of the target if it exists in the array, or -1 if it doesn't.
Java Solution:
class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
}
// Check if the 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;
}
}
C++ Solution:
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
}
// Check if the 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;
}
};
Explanation: This problem requires a modified binary search. At each step, we determine which half of the array is sorted and then check if the target lies within that sorted half. If it does, we continue searching in that half; otherwise, we search in the other half.
These problems demonstrate how Binary Search can be adapted to solve more complex searching problems efficiently. Understanding these variations is crucial for mastering Binary Search and performing well in coding interviews.