[JS] 코딩 테스트 문제 : 이분검색 [이진 탐색]

문제 : 이분검색

문제 설명

임의의 N개의 숫자가 입력으로 주어집니다. N개의 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어지면 이분검색으로 M이 정렬된 상태에서 몇 번째에 있는지 구하는 프로그램을 작성하세요. 단 중복값은 존재하지 않습니다.

▣ 입력설명

첫 줄에 한 줄에 자연수 N(3<=N<=1,000,000)과 M이 주어집니다.
두 번째 줄에 N개의 수가 공백을 사이에 두고 주어집니다.

▣ 출력설명

첫 줄에 정렬 후 M의 값의 위치 번호를 출력한다.

▣ 입력예제 1

8 32
23 87 65 12 57 32 99 81

▣ 출력예제 1

3

내코드

function solution(target, arr) {
  let answer = null;
  // 숫자들을 오름차순 정렬 후 순서에 맞는 번호를 1 부터 차례로 부여해 배열로 저장
  let sortArr = arr
    .sort((a, b) => a - b)
    .map((num, index) => [num, index + 1]);

  console.log(sortArr);

  // 배열의 값이 하나 남을 때 까지 반복
  while (sortArr.length > 0) {
    let centerIdx = Math.floor(sortArr.length / 2); // 기준이 될 인덱스
    const [num, index] = sortArr[centerIdx]; // 기준이 될 숫자와 번호

    console.log(`기준 인덱스:${centerIdx} 기준 값 ${num}`);

    if (num > target) {
      sortArr = sortArr.slice(0, centerIdx); // 배열의 0번부터 기준값 이전의 값까지 잘라내 저장
      console.log("# 기준값 이전의 배열", sortArr);
    } else if (num < target) {
      sortArr = sortArr.slice(centerIdx + 1); // 기준값 다음 번호부터 배열의 마지막 번호까지 잘라내 저장
      console.log("# 기준값 이후의 배열", centerIdx, sortArr);
    } else {
      answer = index;
      console.log("# 위치 특정 완료");
      break;
    }
  }
  return answer;
}

풀이

1. 숫자들을 오름차순 정렬 후 순서에 맞는 번호를 1 부터 차례로 부여해 배열 sortArr 로 저장 ([[값, 번호], ...])
2. 배열의 값이 하나 남을 때 까지 반복하면서 현재 배열의 중앙 인덱스를 변수 centerIdx 로 선언하여 현재 배열의 centerIdx 의 숫자와 입력된 숫자를 비교
3. 대소관계 여부에 따라 기준 값 이후나 이전의 배열의 요소들로만 다시 배열을 구성 하고 만약 숫자를 비교해서 같은 경우에는 그 번호 값을 정답 변수에 저장하고 반복문에서 벗어나 정답 번호를 반환

다른 해결 방법

// 정답지 방법
function solution(target, arr) {
  let answer;
  arr.sort((a, b) => a - b); // 숫자들을 오름차순 정렬

  // lt 시작 인덱스, rt 끝 인덱스
  let lt = 0,
    rt = arr.length - 1;

  // 시작 인덱스가 끝 인덱스와 같거나 작아질 때 까지 반복
  while (lt <= rt) {
    // 시작 인덱스 값과 끝 인덱스 값을 2 로 나눠 기준이될 중앙 인덱스 mid 을 설정
    let mid = parseInt((lt + rt) / 2);
    // 기준값과 target 이 동일하다면 정답으로 간주 인덱스 값에 + 1 위치 번호를 저장
    if (arr[mid] === target) {
      answer = mid + 1;
      break;
    }
    // 기준값이 target 보다 큰경우 끝 인덱스를 중앙인덱스에 - 1 로 저장
    else if (arr[mid] > target) rt = mid - 1;
    // 기준값이 target 보다 작은경우 시작 인덱스를 중앙인덱스에 + 1 로 저장
    else lt = mid + 1;
  }

  return answer;
}

풀이

1. 숫자들을 오름차순 정렬하고 시작 인덱스와 끝 인덱스 나타낼 lt, rt 변수를 생성
2. 시작 인덱스가 끝 인덱스와 같거나 작아질 때 까지 반복하면서 시작 인덱스 값과 끝 인덱스 값을 2 로 나눠 기준이 될 중앙 인덱스 변수 mid 을 선언
3. 기준 값이 target 보다 큰 경우 끝 인덱스를 중앙 인덱스에 - 1 로 저장, 기준 값이 target 보다 작은 경우 시작 인덱스를 중앙 인덱스에 + 1 로 저장 만약 기준 값과 target 이 동일한 경우 정답으로 간주해 반복 인덱스 값에 + 1 위치 번호를 저장하고 반복문에서 벗어나 정답 번호를 반환

---

참고

https://www.inflearn.com/course/%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4/dashboard