Inclusive Boundary Search Template
In this Template, the search space is defined by an inclusive range [left, right], starting with left at 0 and right at arr.length - 1. The pointers move inward using explicit step reductions (left = mid + 1 or right = mid - 1) until left exceeds right.
Common use cases: Exact target lookup, finding first and last occurrences of an element, and target-based range searches in sorted arrays.
Basic Template Structure:
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
// code
left = mid + 1;
right = mid - 1;
}Scenario 1: – Target specific equality check. If the element at mid equals our target value.
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
// code
if (nums[mid] == target) {
// Target found or condition satisfied
}
}Scenario 2: – Less than check. If the element at mid is strictly less than our target value, the target must lie in the right half of the array.
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
// code
if (nums[mid] < target) {
left = mid + 1;
}
}
Scenario 3: – Greater than check. If the element at mid is strictly greater than our target value, the target must lie in the left half of the array.
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
// code
if (nums[mid] > target) {
right = mid - 1;
}
}
Final Template: – combined all the scenarios into a single structure with generic parameters
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
// code
if (param1 == param2) {
// Target found or condition satisfied
} else if (param1 < param2) {
left = mid + 1;
} else {
right = mid - 1;
}
}