개념

1. 탐색의 범위를 절반씩 좁혀가며 데이터 탐색하는 알고리즘
2. 데이터가 정렬되어진 상태여야만 사용가능
3. 입력 데이터 많을 때 or 탐색의 범위가 넓을 때 효과적임

동작

필요요소: arr , startIdx , endIdx , midIdx , target

1. startIdx와 endIdx 로 midIdx 구함 (소수점 버리는 걸로)
2. arr [ midIdx ] 와 target 값을 비교
3. arr [midIdx ] > target 일 때 endIdx = midIdx - 1 로 설정
4. arr[ midIdx ] < target 일 때 startIdx = midIdx + 1 로 설정
5. arr[ midIdx ] == target 일때 까지 2,3,4 과정 반복

시간복잡도

이진탐색은 진행할 때 마다 중간을 기준으로 탐색해야하는 데이터의 개수를 절반씩 줄여 나가기 때문에 시간복잡도 O(log N)

최악의 경우에 (1/2)^k * N = 1 이 될 때까지 탐색을 하게 되기때문에 k = logN 이 되어 O(logN)의 시간복잡도를 가진다.

확인하는 데이터의 개수가 절반씩 줄어드는 특징 → 퀵정렬과 동일하다.

📌구현

1.재귀

def search(arr,target,start,end):
    if start>end:
        return None
    mid=(start+end)//2
    
    if arr[mid]==target:
        return mid
    
    elif arr[mid] > target:
        return search(arr,target,start,mid-1)
        
    else:
        return search(arr,target,mid+1,end)

2.반복문

def binary_search(arr, target, start, end):
    while start<= end:
        mid= (start+end)//2
        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            end=mid-1
        else:
            start=mid+1
    return start

경험상 마지막 부분 return start는 while 문 조건이 start <= end 로 끝나야 반복문이 종료되기 때문이다.

start:0 end:1 mid:0 arr[mid]:10 cur:5
> start:0,end:-1,mid:0
> return 0

start:0  end:0 mid:0 arr[mid]:10 cur:15
> start:1,end:0,mid:0
> return 0

📌추가

이진 검색은 구간을 탐색하는데 사용한다.
내가 매번 실수하는 부분이라서 다음 문제의 후기를 잊어버릴 때마다 읽어 보자

• 백준2343:기타 레슨