704. Binary Search

// 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.
// O(log n) gets exponentially smaller after splitting in half. Continue to cut in half.
// Binary search is a divide and conquer algo each step halves the elements it searches through. 

// 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.

// ----------------------------------------------------------------
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
// return the index of the target in nums
// continue halving with a while loop 
var search = function(nums, target) {
    // The first step is to create variables for the min and 
    // max indicies.  This helps us bucket the inner array we
    // are searching through.
    let min = 0;
    let max = nums.length - 1;
    // create a while that allows us to serach for the the item
    // so long our min variable is less than or equal to our max
    while (min <= max) {
            // Create a midpoint in loop using the min and max to start
            // our search. min + max / 2
        let mid = Math.floor((min + max) / 2)
        if (target == nums[mid]) {
            return mid
        }
        // if the item does not equal our original midpoint, we need to 
        // determine which half of the array we should begin to check.
        // If the item is less than our starting midpoint, we need to 
        // adjust our max to now focus on the first half of our array.
        else if (target < nums[mid]) {
            max = mid - 1;
        }
        // If the item is greater than our starting midpoint, we need to 
        // adjust our min to now focus on the second half of our array.
        else {
            min = mid + 1;
        }
    }
    // If our target is not inside of our element, return the sentinal value
    return -1;
};