# 704 Binary Search

## Problem Statement

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.
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4

## Approach

Two Pointers Low and High used as boundaries

## Solution

``````var search = function(arr, val) {
let low = 0
let high = nums.length-1

while (low < high) {
let mid = low + Math.floor((high - low + 1) / 2);
if (target < nums[mid]) {
high = mid - 1
} else {
low = mid
}
}
return nums[low] === target ? low : -1
}
``````

## Questions

• How are we looping?
We are using a while loop that runs while low < high. Once that loops stops running we know that they are pointing to the same element.
• How are we building the mid point?
`low + Math.floor((high - low + 1) / 2)` calculates the index of the mid point relative to the current subarray. Without adding low we would calculate the mid-index of the whole array.

LC

Searching