daily 알고리즘 : binarySearch

소히·2022년 7월 13일

binary_search 알고리즘 이진탐색

알고리즘Daily

목록 보기

1/22

binarySearch

문제

오름차순 정렬된 정수의 배열(arr)과 정수(target)를 입력받아 target의 인덱스를 리턴해야 합니다.

입력

인자 1 : arr

number 타입을 요소로 갖는 배열
arr[i]는 정수

인자 2 : target

number 타입의 정수

출력

number 타입을 리턴해야 합니다.

주의사항

이진탐색 알고리즘(O(logN))을 사용해야 합니다.
단순한 배열 순회(O(N))로는 통과할 수 없는 테스트 케이스가 존재합니다.
target이 없는 경우, -1을 리턴해야 합니다.

입출력 예시

let output = binarySearch([0, 1, 2, 3, 4, 5, 6], 2);
console.log(output); // --> 2

output = binarySearch([4, 5, 6, 9], 100);
console.log(output); // --> -1

풀이

arr의 왼쪽 끝 인덱스(start)와 오른쪽 끝 인덱스(end)를 선언한다.
왼쪽 끝 인덱스와 오른쪽 끝 인덱스의 중간점인 middle을 선언한다.
while문을 돌면서 arr[middle]값이 target과 같아질 때까지 계속 중간점을 찾아 리턴한다.

const binarySearch = function (arr, target) {
  // start : arr 왼쪽 끝 인덱스
  // end : arr 오른쪽 끝 인덱스
  let start = 0;
  let end = arr.length - 1;
  while (start <= end) {
    let middle = Math.floor((start + end) / 2);
    // 결국 arr[middle]이 target값과 같아지면 middle를 리턴한다.
    if (arr[middle] === target) {
      return middle;
    }
    // 중간값 탐색을 하면서 범위를 계속 좁혀 나간다
    if (arr[middle] > target) {
      end = middle - 1;
    } else {
      start = middle + 1;
    }
  }
  return -1; // target이 없을 경우 -1 리턴
};

다른 풀이

const binarySearch = function (arr, target) {
  const rec = function (start, end) {
    let middle = Math.floor((start + end) / 2);
    // Base Case
    // start와 end값이 같아졌을 때 조건대로 return 한다
    if (start === end) {
      return arr[middle] === target ? middle : -1;
    }
    // Recursice Case
    else if (arr[middle] >= target) {
      return rec(0, middle);
    } else {
      return rec(middle + 1, end);
    }
  };
  return rec(0, arr.length - 1);
};