IF - 이진검색

문제

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

예시

Input1	Input2	Output
[7, 28, 43, 67, 88, 92, 100]	100	7
[23, 87, 65, 12, 57, 32, 99, 81]	32	3

풀이 및 회고

1. 이진검색을 활용해 주어진 배열에서 원하는 값의 위치를 찾아내는 문제이다.
2. 배열 양 끝을 가리키는 포인터 lp와 rp를 둔다.
3. 두 포인터로부터 같은 거리에 있는 원소(가운데 원소)가 찾고자 하는 값과 같으면 해당 원소의 인덱스가 찾고자 하는 인덱스이다.
4. 반대로 원소가 찾고자 하는 값보다 크면 rp를 중앙보다 앞으로 한 칸 땡기고, 찾고자 하는 값보다 작으면 lp를 중앙보다 뒤로 한 칸 밀어낸다.
5. 3~4 번 과정을 재귀함수로 반복하면, lp와 rp의 중앙 값이 찾고자 하는 값과 같아지는 순간이 온다. 이 때 중앙 값의 인덱스를 반환한다.
6. 만약 lp가 rp 보다 커진다면 찾고자 하는 값이 배열에 없다는 뜻이다.

• 처음에는 포인터 없이 주어진 배열을 slice 메서드로 계속 반으로 자르는 방법을 생각했었는데, 서브 배열을 만들면 찾아낸 값이 원본 배열에서 몇 번째 인덱스에 있는지 알아내기가 어려웠다.
• 대신 포인터를 사용하면 두 포인터의 값이 곧 원본 배열에서의 인덱스이므로, 인덱스를 구할 수 있었다.

코드

const solution = (arr, num) => {
  arr.sort((a, b) => a - b);
  let answer;

  const lp = 0;
  const rp = arr.length - 1;

  answer = recursion(arr, num, lp, rp);
  if (answer === 'None') return 'None';
  else return answer;
};

const recursion = (arr, num, lp, rp) => {
  const center = Math.floor((lp + rp) / 2);
  if (arr[center] === num) return center;
  else if (arr[center] > num) rp = center - 1;
  else if (arr[center] < num) lp = center + 1;
  if (lp > rp) return 'None';
  else return recursion(arr, num, lp, rp);
};