Binary Search

Binary Search - LeetCodeLeetCode

Problem

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target 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)