[파이썬 알고리즘 문제풀이] : 이분 검색

문제

n개의 숫자가 주어진다. n개의 수를 오름차순 정렬하고 n개의 수 중 한 개의 수인 m이 주어지면 이분 검색으로 m이 정렬된 상태에서 몇 번째에 있는지 구하라.

해결

주어지는 수의 총 개수는 n
정렬하고 몇 번째에 있는지 찾아야 하는 수는 m
n의 수 만큼 주어지는 랜덤 수는 a

---

m은 a에 꼭 포함되어 있다.

조건을 먼저 잘 생각해 본다.

a.sort()

정렬된 상태에서 m이 몇 번째에 존재하는지 찾아야 한다. 주어지는 수들이 들어있는 list인 a를을 일단 정렬한다.

lt = 0
rt = n - 1

처음(lt)과 끝(rt)를 선언해 준다.

while lt <= rt:

while문을 통해 lt가 rt보다 작거나 같을 때 까지 반복되게 한다.

mid = (lt + rt) // 2

이분 검색을 하기 위해 mid는 lt와 rt의 값 중앙을 끊도록 해준다.

    if a[mid] == m:
        print(mid + 1)
        break
    elif a[mid] > m:
        rt = mid - 1
    else:
        lt = mid + 1

a[mid]가 m과 같으면 값을 출력하고 브레이크를 걸어준다.

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