이분탐색

 문제에 앞서 이분 탐색(Binary Search)이 무엇인지, 언제 사용하는 것인지에대해 알아보겠습니다. 

이분 탐색이 가능한 주요 조건은 정렬되어 있어야 한다는 것입니다. 정렬되어 있는 배열에서 데이터를 찾으려고 시도할 때, 순차탐색처럼 처음부터 끝까지 하나씩 모든 데이터를 체크하면서 값을 찾는 것이 아니라 탐색 범위를 절반 씩 줄여가며 찾아가는 탐색법입니다. 아래 문제를 이분탐색법을 이용하여 풀어보겠습니다.

 

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

▣ 입력설명

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

▣ 출력설명

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

▣ 입력예제

8 32

23 87 65 12 57 32 99 81

▣ 출력예제

3

import sys
sys.stdin=open("input.txt", "rt")

n, m=map(int, input().split())
a=list(map(int, input().split()))
a.sort()
lt=0
rt=n-1
while lt<=rt:
    mid=(lt+rt)//2
    if a[mid]==m:
        print(mid+1)
        break
    elif a[mid]>m:
        rt=mid-1
    else:
        lt=mid+1

index	0	1	2	3	4	5	6	7
a	12	23	32	57	65	81	87	99

 입력값을 a라는 list에 받고 정렬(sort)하게되면 위의 사진과 같이 리스트가 정렬됩니다.

그리고 0번 index(0)부터 n번까지의 index(n-1)의 범위를 구하기 위해 lt와 rt라는 변수를 만들어줍니다.

그렇다면 lt와 rt를 합한 값을 2로 나눠준다면, index의 중간값이 도출될겁니다.

도출된 값이 a[mid]에 대입하여 그 값이 m인지 판별한다면 그대로 출력한 뒤 break 됩니다.( (mid+1)번의 index값)

 이제 그 값이 그렇지 않다면 rt를 mid-1 (32)해주어 범위를 줄여줍니다.

작은 쪽의 범위를 버릴 때는 lt=mid+1이 되어 a[mid]와 m의 값이 같아질겁니다.

 a[mid]==m이면 출력하면 되기 때문에, 3이라는 값을 출력합니다.