백준 10815번 (이진탐색)

처음에는 그냥 리스트 메소드 중 count를 이용해서 해봤는데 아니나 다를까 바로 시간초과가 나왔다.

N이 오십만 까지 입력되기 때문에 시간단축을 위해 sys입력과 이진탐색을 모두 사용했다.

 

이진탐색이란 오름차순 정렬된 배열에 사용하는 탐색방법이다.

그러니 먼저 L1.sort()를 해주고, 이진탐색함수를 정의해주자.

매개변수로는 배열(array)과 찾는 수(target)와 시작점(start) 끝점(end)을 받는다.

알고리즘은 매우 간단하다. 배열을 반으로 나누어 찾는 수가 작은 쪽에 있으면 end를 중간 수에서 바로 전 수(mid-1)로 지정해 작은 쪽에서 다시 진행하고 큰 쪽에 있으면 시작점을 중간 수 바로 다음 수(mid+1)로 지정해 큰 쪽에서 다시 진행한다. 이 과정을 정확히 중간 수(mid)에 찾는 수가 올 때까지 반복한다. 만약 찾는 수가 배열안에 없었다면 None이 반환된다.