[이코테] 이진 탐색_정렬된 배열에서 특정 수의 개수 구하기(자바스크립트)

이번 글은 '이것이 취업을 위한 코딩테스트다' 내의 문제를 풀고 정답 코드를 정리한 것입니다.

이것이 취업을 위한 코딩 테스트다 with 파이썬 | 나동빈 - 교보문고

---

👨‍💻 문제

---

정답 코드

---

문제 풀이

  문제에서 요구하는 시간 복잡도는 O(logN)이므로 선형 탐색으로 문제를 해결할 수 없다. 따라서 이진 탐색을 통해 문제를 풀어야 한다.

 배열은 정렬된 채로 주어지기 때문에 수열 내에 x가 존재한다면 연속해서 나열되어 있음을 예상할 수 있다. 따라서 x가 처음 등장하는 인덱스와 마지막으로 등장하는 인덱스를 각각 계산한 뒤, 두 인덱스의 차이를 반환하면 된다. 이 같은 과정을 이진 탐색 2개를 만들어 처리한다.

 아래 그림과 같이 배열이 주어지고 찾고자 하는 값이 2라면 2가 등장하는 처음 및 마지막 위치를 찾는 것이다.