이분 검색: 범위를 반으로 나누면서 해당값을 찾는다
log2(N) 횟수만 찾으면 해당값의 위치를 알 수 있다
문제: 임의의 n개의 숫자가 입력으로 주어진다. n개의 수를 오름차순으로 정렬한 다음 n개의 수 중
한 개의 수인 m이 주어지면 이분 검색으로 m이 정렬된 상태에서 몇 번째에 있는지 구하는 프로그램을
작성하시오.
n, m =map(int, input().split())
#n: 주어지는 숫자의 개수 m:찾고자 하는 수
num_list=list(map(int, input().split()))
num_list.sort()
#정렬 함수 sort()
lt=0 #left-->lt
rt=n-1 #right-->rt
while lt<=rt:
mid=(lt+rt)//2 #중간값 지정
if num_list[mid]==m:
print(mid+1)
break
#중간값 위치의 수가 찾고자 하는 수와 일치할 경우 루프 종료
elif num_list[mid]>m:
rt=mid-1
#중간 위치의 숫자가 찾고자 하는 수보다 큰 경우
#찾는 값이 중간 위치보다 왼쪽에 위치하므로 rt를 mid-1의 값으로 지정
else:
lt=mid+1
#중간 위치의 숫자가 찾고자 하는 수보다 작은 경우
#찾는 값이 중간 위치보다 오른쪽에 위치하므로 lt를 mid+1의 값으로 지정
5.1 가장 큰 수 (스택) (0) | 2021.07.19 |
---|---|
4.4 마구간 정하기 (결정 알고리즘) (0) | 2021.07.15 |
4.3 뮤직비디오(결정 알고리즘) (0) | 2021.07.14 |
4.2 랜선 자르기(결정 알고리즘) (0) | 2021.07.13 |
3.1 회문 문자열 검사 (0) | 2021.07.12 |
댓글 영역