파이썬 알고리즘 022 | 이분검색

22. 이분검색

임의의 N개의 숫자가 입력으로 주어집니다. N개의 수를 오름차순으로 정렬한 다음 N개의 수
중 한 개의 수인 M이 주어지면 이분검색으로 M이 정렬된 상태에서 몇 번째에 있는지 구하는
프로그램을 작성하세요. 단 중복값은 존재하지 않습니다.
▣ 입력설명
첫 줄에 한 줄에 자연수 N(3<=N<=1,000,000)과 M이 주어집니다.
두 번째 줄에 N개의 수가 공백을 사이에 두고 주어집니다.
▣ 출력설명
첫 줄에 정렬 후 M의 값의 위치 번호를 출력한다.
▣ 입력예제 1
8 32
23 87 65 12 57 32 99 81
▣ 출력예제 1
3

<내 풀이>

[이분 검색 적용 x]

n, m = map(int, input().split())
a=list(map(int, input().split()))
b=sorted(a)
b=b.index(m)
print(b+1)

<풀이>

n, m = map(int, input().split())
a=list(map(int, input().split()))
a.sort() #기본값으로 항상 정렬해두어야 한다
lt=0
rt=n-1 #(인덱스 넘버니깐)
while lt<=rt : 
    mid = (rt+lt)//2 
    if a[mid] == m :
        print(mid+1) #현재 mid는 인덱스라서 1해줘서 자릿값을 출력해준다
        break
    elif a[mid] > m :
        rt=mid-1
    else : 
        lt = mid+1

<반성점>

• 이분검색이 뭔지 몰라서 그냥 편법으로 사용하였다
  이분 검색의 개념을 잘 이해하고 앞으로 사용하도록 하자

<배운 점>

• index :리스트에서 어떤 값의 인덱스 번호 알고 싶을 때
  특정 항목이 리스트에서 어디있는지 찾을 때

a = ["Woosung", "Bosung", "Seungbum", "Jihoon", "Joonghoon","Sunggi"]
print a.index("Bosung")

=> 보성의 인덱스 번호 1이 출력된다

-이진 탐색(Binary Search) :
배열이 정렬되어 있는 상태에서, 원하는 값이 중간값보다 큰지 작은지를 살펴본다. 중간값(mid) = (왼쪽인덱스lt+오른쪽인덱스rt)//2이고 중간값이 더 크면 왼쪽을 날리고 작으면 오른쪽을 날린 후 mid값을 조정해준다. 그리하여 lt>rt가 될 때까지 반복한다.

• lt 가 rt보다 커져버리면 탐색이 끝난 것이다

• 이분 검색을 하기 위해서는 기본적으로 오름차순 혹은 내림차순
  정렬을 해야함 - 전제 : 오름차순 / 내림차순

-이분 검색은 검색 알고리즘에서 주로 사용된다, 결정 알고리즘으로 풀 수 있는 문제들은 이러한 특징이 있다 - 찾고자 하는 답이 어떤 범위 안에 있음을 알 수 있다, 이때 이분 검색을 사용해 범위를 좁혀나가는 것