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
js
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
js
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
js
// 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 = 1
Working Example
Type yarn test on console to run vitest.