# [이.취.코] Chap 15. 이진탐색 - Q27. 정렬된 배열에서 특정 수의 개수 구하기

- Author: @mildsalmon
- Published: 2021-10-09
- Updated: 2021-10-09
- Source: http://blex.me/@mildsalmon/%EC%9D%B4%EC%B7%A8%EC%BD%94-chap-15-%EC%9D%B4%EC%A7%84%ED%83%90%EC%83%89-q27-%EC%A0%95%EB%A0%AC%EB%90%9C-%EB%B0%B0%EC%97%B4%EC%97%90%EC%84%9C-%ED%8A%B9%EC%A0%95-%EC%88%98%EC%9D%98-%EA%B0%9C%EC%88%98-%EA%B5%AC%ED%95%98%EA%B8%B0
- Tags: 파이썬, 한빛미디어, 나동빈, 코딩테스트, 문제, 풀이, 이진탐색

---

# 1. 정렬된 배열에서 특정 수의 개수 구하기

- 난이도
	- 중
- 풀이 시간
	- 30분
- 시간 제한
	- 1초
- 메모리 제한
	- 128 MB
- 출처
	- Zoho 인터뷰

### A. 📜 문제

N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있다. 이때 이 수열에서 x가 등장하는 횟수를 계산하라.

단, 이 문제는 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 시간 초과 판정을 받는다.

##### a. 예를 들면. 

수열 {1, 1, 2 ,2 ,2 ,2, 3}이 있을 때 x=2라면, 현재 수열에서 값이 2인 원소가 4개이므로 4를 출력한다.

##### b. 입력 조건

- 첫째 줄에 N과 x가 정수 형태로 공백으로 구분되어 입력된다.
	- 1 <= N <= 1,000,000
	- -1e9 <= x <= 1e9
- 둘째 줄에 N개의 원소가 정수 형태로 공백으로 구분되어 입력된다
	- -1e9 <= 각 원소의 값 <= 1e9

##### c. 출력 조건

수열의 원소 중에서 값이 x인 원소의 개수를 출력한다. 단 값이 x인 원소가 하나도 없다면 -1일 출력한다.

##### d. 테스트 케이스

- 입력 예시

	```

	7 2
	1 1 2 2 2 2 3

	```

	```

	7 4
	1 1 2 2 2 2 3
	
	```

- 출력 예시

	```

	4

	```

	```

	-1

	```

### B. 💡 내 답안

##### a. 😊 1차 시도 (성공)

```python

def bi_sec(start, end, target, array):
    while start <= end:
        mid = (start + end) // 2

        if array[mid] == target:
            return mid

        if array[mid] > target:
            end = mid -1
        elif array[mid] < target:
            start = mid + 1
    return 0

n, x = list(map(int, input().split()))
array = list(map(int, input().split()))

start = 0
end = n-1

pre = bi_sec(start, end, x-1, array)
post = bi_sec(start, end, x+1, array)

answer = (post - 1) - (pre + 1) + 1

if post - pre > 0:
    print(answer)
else:
    print(-1)

```

##### a. 🙄 회고

> 내 풀이

- logN으로 탐색하는 것에서 이진탐색이 떠올랐다.

> 반성

- 이진탐색 라이브러리도 있는데, 사용하지 못했다.
	- bisect

> 결론

- 다음에 풀때는 이진탐색 라이브러리도 사용해봐야지

### C. 🧐 문제 해설

> 이해한 내용을 바탕으로 작성했습니다.

이진 탐색을 2번 돌리면 된다.

N개의 원소가 정수이기 때문에, `구하고자 하는 수 - 1`과 `구하고자 하는 수 + 1`의 인덱스를 따로 구해서 빼주면 된다.

##### a. 책 답안

[python-for-coding-test/1.py at master · ndb796/python-for-coding-test (github.com)](https://github.com/ndb796/python-for-coding-test/blob/master/15/1.py)

# 참고문헌

나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년