LeetCode: Binary Search Solution

Approach

Given that the array is sorted ascending

Compare the middle element with

• if greater than, continue searching on the left
• if smaller than, continue searching on the right
• else we are done

Implementation

1var search = function (nums, target) {
2  const n = nums.length
3  let lo = 0
4  let hi = n - 1
5  let res = -1
6
7  while (lo <= hi) {
8    let mid = Math.floor((lo + hi) / 2)
9    if (nums[mid] > target) {
10      hi = mid - 1
11    } else if (nums[mid] < target) {
12      lo = mid + 1
13    } else {
14      res = mid
15      break
16    }
17  }
18
19  return res
20}

References

Codility's Material

LeetCode's official solution

Original problem