Searching
Binary Search
- Initialize
leftandrightpointers to the start and end of the array - While
leftis less than or equal toright- Calculate the middle index
- If the middle element is the target, return the index
- If the middle element is less than the target, move the
leftpointer to the middle + 1 - If the middle element is greater than the target, move the
rightpointer to the middle - 1
- If the target is not found, return -1
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}Key Points
- The array must be sorted for binary search to work
- The time complexity is O(log n)
- The space complexity is O(1)
Variants
Binary Search with Recursion
function binarySearchRecursive(arr, target, left, right) {
if (left > right) {
return -1;
}
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
return binarySearchRecursive(arr, target, mid + 1, right);
} else {
return binarySearchRecursive(arr, target, left, mid - 1);
}
}Binary Search with same elements
function binarySearchSameElements(arr, target) {
let left = 0;
let right = arr.length - 1;
let result = -1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
result = mid;
right = mid - 1;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}Explanation: For the same elements, we need to find the first occurrence of the target. So we need to move the right pointer to the middle - 1 when the middle element is equal to the target. This way, we will find the first occurrence of the target.