이분검색

절반씩 범위를 줄여나가면서 검색하는 방법

• 정렬이 되어 있어야 한다
  정렬을 하는데 시간이 꽤 걸리지만 여러번 찾아야 할 때 좋다

일상생활속에서 이분검색하기

게임을 할 때 1-50의 숫자들 중에 하나를 술래가 정하고 나머지 사람들이 맞춘다고 하자
빨리 범위를 줄이기 위해서 우리는 중간값인 25를 처음 숫자로 말할것이다
그럼 술래가 up or down 을 말하고 up이면 26~50의 중간값을 말하며 범위를 줄여나갈 것이다
이렇게 일상속에서 우리가 자연스럽게 사용하는 알고리즘을 컴퓨터는 코드로 표현해줘야 실행할 수 있다

문제

targetNumber와 배열 주어졌을 때 정렬후 targetNumber가 배열의 몇번째에 있는지 구하시오
32, [23, 87, 65, 12, 57, 32, 99, 81]

이분검색 코드로 표현하기

      function solution(targetNumber, numbers) {
        numbers.sort((a, b) => a - b);
        console.log(numbers);
        let startIndex = 0;
        let endIndex = numbers.length - 1;
        while (startIndex <= endIndex) {
          let middleIndex = Math.floor((startIndex + endIndex) / 2);
          if (numbers[middleIndex] === targetNumber) return middleIndex + 1;
          else if (targetNumber < numbers[middleIndex])
            endIndex = middleIndex - 1;
          else startIndex = middleIndex + 1;
        }
        return 0;
      }

      console.log(solution(32, [23, 87, 65, 12, 57, 32, 99, 81]));

계속 이분검색을 하다보면 startIndex와 endIndex가 같아지는 지점이 오는데 그럴때는 middleIndex===startIndex===endIndex가 되어 해당 numbers[middleIndex]가 targetNumber인지 비교 해준다
만약 targetNumber가 배열에 존재하지 않다면 이분검색을 끝내도 정답이 없게 되고 0을 return하도록 해주었다
처음에 while문을 numbers[middleIndex]!==targetNumber라고 작성했었는데
만약 숫자가 배열에 없다면 indexOf 쓰거나 하면 되긴 하지만
스코프 때문에 middleIndex를 2번 선언해줘야 하고 해서 위 코드가 좀더 좋아보였다

출처 자바스크립트 알고리즘 문제풀이