[Python-CodingTest] 4-1. 이분검색

이분검색

문제 정리

입력

8 32 // n m
23 87 65 12 57 32 99 81 // 요소가 n개인 리스트

처리 과정

1. 리스트 오름차순 정렬
2. 리스트의 양 끝 요소를 가리키는 두 개의 포인터(p1,p2) 설정
3. (p1+p2)//2인 mid 설정
4. lst[mid]가 찾고자하는 값(m)이랑 같다면 반복문 종료 후 mid+1 출력 (mid는 인덱스 값이기 때문에 요소가 몇번째인지 출력할 때에는 mid+1)
5. lst[mid]>m라면 p2를 mid-1로 변경
6. lst[mid]<m라면 p1를 mid+1로 변경
7. 3~6을 반복

출력

3

내 답

import sys
sys.stdin = open("./input/in1-1.txt", "rt")

n,m=map(int, input().split())
lst=list(map(int, input().split()))

lst.sort()

p1=0
p2=n-1

while True:
    mid=(p1+p2)//2
    if lst[mid]==m:
        print(mid+1)
        break
    elif lst[mid]>m:
        p2=mid-1
        continue
    else:
        p1=mid+1
        continue

풀이

import sys
sys.stdin = open("./input/in1-1.txt", "rt")

n,m=map(int, input().split())
lst=list(map(int, input().split()))

lst.sort()

p1=0
p2=n-1

while p1<=p2:
    mid=(p1+p2)//2
    if lst[mid]==m:
        print(mid+1)
        break
    elif lst[mid]>m: # 찾고자 하는 값이 lst[mid]보다 작으니까 오른쪽 범위 날리기
        p2=mid-1
    else: # 찾고자 하는 값이 lst[mid]보다 크니까 왼쪽 범위 날리기
        p1=mid+1

정리

• 이분검색의 전제조건은 오름차순 혹은 내림차순 “정렬”

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기