Understanding binary search.
Basic Implementation
int binarySearch(vector& arr, int target) {
int left = 0;
int right = int(arr.size()) - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
// do something;
return mid;
}
if (arr[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
// target is not in arr, but left is at the insertion point
return left;
}
When there are duplicates
Finding the lower bound of the target
int binarySearch(vector& arr, int target) {
int left = 0;
int right = arr.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] >= target) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
Finding the upper bound of the target
int binarySearch(vector& arr, int target) {
int left = 0;
int right = arr.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] > target) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}