이진탐색

이진탐색이란?

검색 범위를 줄여나가면서 원하는 데이터를 검색하는 알고리즘

오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘

처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식

 

이진탐색 예시

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

n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
l=0
r=n-1

while l<=r:
    mid=(r+l)//2
    if a[mid]==m:
        print(mid+1)
        break
    elif a[mid]<m:
        l=mid+1
    elif a[mid]>m:
        r=mid-1

[23,87,65,12,57,32,99,81] 의 배열이 주어지고 32를 찾아야하는 경우

1. 배열을 오름차순 정렬한다. [12, 23, 32, 57, 65, 81, 87, 99] 

2. 왼쪽끝, 오른쪽끝, 중간값을 지정해준다.

   lt=0(배열의 시작) , rt=n-1(배열의 끝), mid=(rt+lt)//2

3. lt<=rt 일 때 까지 이진탐색을 시작한다. lt와 rt가 같아진다면 원하는 값이 없는 경우

4. 만약 mid 값보다 찾는 값이 작다면 오른쪽 끝을 mid-1 로 지정해서 범위를 줄인다.

5. mid 값보다 찾는 값이 크면 왼쪽 끝을 mid+1로 해서 범위를 줄인다.

6. 원하는 값을 찾을 때까지 반복해준다.

 

시간복잡도

위의 예제 8개의 배열을 이진탐색으로 진행하면 배열의 크기가

8 -> 4 -> 2 ->1 로 줄어들고 3회 탐색이 수행되었다. 시간복잡도는 3이된다.

N개 크기의 배열을 이진 탐색한다면 N->N/2->N/4-> ..->N/2^K->.. ->1로 실행된다.

배열의 크기를 N으로 본다면 2^K=N 일때 K가 실행횟수, 즉 시간복잡도가 된다.

K=log2N 이므로 이진탐색의 시간복잡도는 O(logN) 이 된다.

 

 

Reference

https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%EA%B2%80%EC%83%89_%EC%95%8C%EA%B3%A0%EB%A