[알고리즘] 이진검색

반복문

const binarySearch = (array, value) => {
  let left = 0;
  let right = array.length - 1;
  let middle = Math.floor((left + right) / 2);

  while (left <= right && array[middle] !== value) {
    if (array[middle] < value) {
      left = middle + 1;
    } else {
      right = middle - 1;
    }
    middle = Math.floor((left + right) / 2);
  }
  return array[middle] === value ? middle : -1;
};

console.log(binarySearch([1, 2, 4, 5, 7, 8, 9], 5)); // 3
console.log(binarySearch([1, 2, 4, 5, 7, 8, 9], 3)); // -1

재귀

const binarySearch = (array, value) => {
  let left = 0;
  let right = array.length - 1;

  const recursive = (start, end) => {
    let middle = Math.floor((start + end) / 2);

    if (array[middle] === value) return middle;

    if (start > end) return -1;

    if (array[middle] < value) {
      return recursive(middle + 1, end);
    } else if (array[middle] > value) {
      return recursive(start, middle - 1);
    }
  };
  return recursive(left, right);
};

console.log(binarySearch([1, 2, 4, 5, 7, 8, 9], 5)); // 3
console.log(binarySearch([1, 2, 4, 5, 7, 8, 9], 3)); // -1