Binary Search
Problem
Given an array of integers
nums
which is sorted in ascending order, and an integertarget
, write a function to searchtarget
innums
. Iftarget
exists, then return its index. Otherwise, return-1
.You must write an algorithm with
O(log n)
runtime complexity.
Example 1:
Input: nums = [-1,0,3,5,9,12], target = 9 Output: 4 Explanation: 9 exists in nums and its index is 4
Example 2:
Input: nums = [-1,0,3,5,9,12], target = 2 Output: -1 Explanation: 2 does not exist in nums so return -1
Constraints:
1 <= nums.length <= 104
-104 < nums[i], target < 104
All the integers in
nums
are unique.
nums
is sorted in ascending order.
Pseudocode
running time of O(log N) doesn't scale linearly with input. vanilla binary search
- ensure that list is sorted
- select a lo and hi point
- in a while loop, calculate a mid point that changes in each interation
- 3 conditions to find a for a target
- if mid-point === target, target found
- if mid-point > target - value is on the left
- reassign hi to mid - 1
- if mid-point < target - value is on the right
- reassign lo to mid + 1
Solution
// Some code
var search = function (nums, target) {
let lo = 0;
let hi = nums.length - 1;
if (nums.length === 1 && nums[0] === target) {
return 0;
}
while (lo <= hi) {
let mid = Math.floor(lo + (hi - lo) / 2);
if (nums[mid] === target) {
return mid;
}
if (nums[mid] > target) {
hi = mid - 1;
}
if (nums[mid] < target) {
lo = mid + 1;
}
}
return -1;
};
Time and Space Complexity
Time
binary search is O(log N)
Total - O(log N)
Space
Constant time operation to store lo, mid, hi values - O(1)
Total - O(1)
Last updated