Description
- Binary search uses divide and conquer approach.
- It has better time complexity than linear search
Prerequisites
- Array has to be sorted
Time & Space Complexity
- Time:
- Best: O(1)
- Average: O(log n)
- Worst: O(log n)
- Space:
- O(1)
Implementation
Iterative
javascript
function iterative(array, target) {
let start = 0;
let end = array.length - 1;
while (start <= end) {
// Calculate middle index
const mid = Math.floor((start + end) / 2);
if (target > array[mid])
start = mid + 1;
else if (target < array[mid])
end = mid - 1;
else
return mid;
}
return -1;
}Recursive
javascript
function recursive(array, target, start, end) {
// Base Case
if (start > end)
return -1;
// Calculate middle index
const mid = Math.floor((start + end) / 2);
if (target > array[mid])
return recursive(array, target, mid + 1, end);
else if (target < array[mid])
return recursive(array, target, start, mid - 1);
else
return mid;
}Possible Test Cases
javascript
// Given array contains target number
const array1 = [2, 3, 4]
const target1 = 3
// Given array does not contain target number
const array2 = [2, 3, 4]
const target2 = 1
// Given array is empty
const array3 = []
const target3 = 1Working Example
Type yarn test on console to run vitest.