# #1 Binary Search

###### tags:`Searching` `Easy`

## Problem
Write a function that takes in a sorted array of integers as well as a target integer. The function should use the Binary Search algorithm to determine if the target integer is contained in the array and should return its index if it is, otherwise `-1`.

If you're unfamiliar with Binary Search, we recommend watching the Conceptual Overview section of this question's video explanation before starting to code.

### Sample Input

array = [0, 1, 21, 33, 45, 45, 61, 71, 72, 73]
target = 33

### Sample Output

3

<br>

## Solutions

### Official 1: recursive

// O(log(n)) time | O(log(n)) space
function binarySearch(array, target) {
  return binarySearchHelper(array, target, 0, array.length - 1);
}
function binarySearchHelper(array, target, left, right) {
  if (left > right) return -1;
  const middle = Math.floor((left + right) / 2);
  const potentialMatch = array[middle];
  if (target === potentialMatch) {
    return middle;
  } else if (target < potentialMatch) {
    return binarySearchHelper(array, target, left, middle - 1);
  } else {
    return binarySearchHelper(array, target, middle + 1, right);
  }
}

<br>

### Official 2: iterative 👍

// O(log(n)) time | O(1) space
function binarySearch(array, target) {
  return binarySearchHelper(array, target, 0, array.length - 1);
}
function binarySearchHelper(array, target, left, right) {
  while (left <= right) {
    const middle = Math.floor((left + right) / 2);
    const potentialMatch = array[middle];
    if (target === potentialMatch) {
      return middle;
    } else if (target < potentialMatch) {
      right = middle - 1;
    } else {
      left = middle + 1;
    }
  }
  return -1;
}

### Optimal Space & Time Complexity

:::spoiler Answer
O(log(n)) time | O(1) space - where n is the length of the input array
:::
---

### Everyone's

:::spoiler 月

/* Time: O(logN), Space: O(1)
   N is the length of array
*/
function binarySearch(array, target) {
    array.sort((a, b) => a - b);
    let startIdx = 0, endIdx = array.length - 1;  
    let midIdx;
    while(startIdx <= endIdx){
        midIdx = Math.floor((startIdx + endIdx) / 2);
        if(target < array[midIdx]) endIdx = midIdx - 1;
        else if(target > array[midIdx]) startIdx = midIdx + 1;
        else return midIdx;
    }
    return -1
}

- `array.sort((a, b) => a - b);`: not need to sort again

:::

<br>

:::spoiler 東

// Time O(log(n)) | Space O(1) - n is the length of input array
function binarySearch(array, target) {
  let left = 0;
  let right = array.length - 1;
  while(left <= right) {
    const mid = Math.floor((left + right) / 2);
    if(array[mid] === target) return mid;
    else if(target < array[mid]) right = mid - 1;
    else left = mid + 1;
  }
  return - 1;
}

:::

<br>

:::spoiler Hao

/**
 * Time complexity: O(logn)
 * Space complexity: O(logn)
 */

function binarySearch(array, target) {
    let start = 0;
    let end = array.length - 1;

    while (end >= start) {
        const mid = Math.ceil((start + end) / 2);
        if (target === array[mid]) return mid;
        else if (target > array[mid]) start = mid + 1;
        else end = mid - 1;
    }

    return -1;
}

- Space complexity: `O(logn)`?
:::

<br>

:::spoiler YC

/*
  time: O(log n) - where n is the length of the given array
  space: O(1)
*/
function binarySearch(array, target) {
  let left = 0;
  let right = array.length - 1;
  while(left <= right){
    const m = Math.floor((left + right)/2);
    if(array[m] === target){
      return m;
    }
    else if(array[m] > target){
      right = m - 1;
    }
    else{
      left = m + 1;
    }
  }

  return -1;
}

:::

<br>

---

## Supplement / Discussion