문제 : binarySearch

오름차순으로 정렬된 배열과 정수를 입력받아 정수의 인덱스를 리턴해야 한다.

• 이진탐색 알고리즘(O(logN))을 사용해야 한다.
• 정수가 없는 경우 -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

문제의 접근

indexof나 for문을 사용한다면 매우 쉽게 풀 수 있을 거라고 생각했다. 하지만 그렇게 한다면 모든 배열을 조회하기 때문에 시간복잡도가 O(n)을 가지게 된다. 문제에서 요구했듯이 이진탐색 알고리즘을 알아야 풀 수 있는 문제다.

그래서 구글링을 통해 이 원리를 이해하고 코드를 작성해보았다.

const binarySearch = function (arr, target) {
  // TODO : 여기에 코드를 작성합니다.
  let start = 0;
  let end = arr.length - 1;
  let mid;
  while(start <= end){
    mid = Math.floor((start + end) / 2)
    if(arr[mid] === target){
      return mid;
    }else if(arr[mid] > target){
      end = mid - 1;
    }else{
      start = mid + 1;
    }
  }
  return -1;
};

위 코드가 이진 탐색의 정석과도 같은 코드다.

문제를 통해 생각해 볼 것

이 문제를 통해서 이진탐색에 대해서 확실하게 이해를 할 수 있었다.
먼저 인덱스의 시작값 start와 인덱스의 마지막 값 end를 정의해주고 그 중간값인 mid를 정의해준다. 그리고 굳이 처음 부터 확인해볼 필요 없이 중간값의 숫자와 비교해서 데이터의 절반을 날릴 수 있다.

중간값 보다 찾는 값이 더 크다면 찾는 값은 중간값 보다 오른쪽에 위치
중간값 보다 찾는 값이 더 작다면 찾는 값은 중간값 보다 왼쪽에 위치

위 사실을 참고해서

• 오른쪽에 있다면 start값을 mid보다 한칸 더 오른쪽으로 설정
• 왼쪽에 있다면 end 값을 mid보다 한칸 더 왼쪽으로 설정

이렇게 설정해서 계속 반복시키면 된다. 언제까지???

바로 arr[min]의 값이 찾는값과 같아질 때 까지
이때는 바로 그 mid의 값이 인덱스가 된다. 만약 같지 않고 while을 빠져나온다면 값이 없다는 뜻이므로 -1이 리턴된다.