Profile
2024년 8월 27일

이분 탐색 알고리즘 [개념]

[11강] 이분 탐색 알고리즘
안녕하세요 Gliver 입니다. 이번 글에서는 이분 탐색 알고리즘에 대해 알아보겠습니다. 목차 이분 탐색 알고리즘 파라매트릭 서치 알고리즘 실제 문제에서 이분 탐색 알고리즘 1. 이분 탐색 알고리즘 이분 탐색 알고리즘은 정렬된 배열에서 특정한 원소를 찾는 알고리즘이다. 정렬된 배열이 아니라면 이분 탐색을 시행할 수 없음. 이분 탐색(binary search)은 범위를 반으로 줄여가며 특정 원소를 찾는 알고리즘으로 예시를 통해서 어떻게 동작하는지 살펴보자. 아래와 같이 정렬된 배열이 있을 때 이분 탐색 알고리즘을 통하여 10을 찾아보자. 방법1 [1단계] left = 0, right = 11 처음에는 배열의 첫 인덱스를 left(0), 끝 인덱스를 right(11)로 지정하고 시작한다. mid = (lef..
[11강] 이분 탐색 알고리즘
https://gliver.tistory.com/31
[11강] 이분 탐색 알고리즘
 

1. 이분 탐색 알고리즘

  • 이분 탐색(Binary Search) 알고리즘은 정렬된 배열에서 특정한 원소를 찾는 알고리즘이다.
    • 정렬된 배열이 아니라면, 이분 탐색 알고리즘은 사용할 수 없다.
 
 

2. 선형 탐색 vs 이분 탐색

  • 선형 탐색
    • 특정한 원소를 선형 탐색으로 찾는다면, 의 시간 복잡도가 걸린다.
    • 정렬이 되어 있지 않은 상태에서도 사용 가능하다.
  • 이분 탐색
    • 특정한 원소를 이분 탐색으로 찾는다면, 의 시간 복잡도가 걸린다.
    • 정렬이 된 상태에서만 사용 가능하다.
 
 

3. 이분 탐색 알고리즘 구현

방법1 -
  • left와 right 변수를 통해서, 원소의 범위를 좁혀나가는 방식이다.
      • notion image
    • 종료 조건: left > right
예제 코드
def binary_search(arr, num): # arr[idx] = num인 idx를 반환
    left = 0
    right = len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2

        if arr[mid] < num: 
            left = mid + 1

        if arr[mid] > num: 
            right = mid - 1
            
        if arr[mid] == num: 
            return mid

    return -1

arr = [1, 2, 4, 5, 7, 9, 10, 12, 14]
print(binary_search(arr, 10))
 
방법2 -
  • 현재 위치 cur과 탐색할 보폭 step을 이용해서, 원소를 찾아가는 방식이다.
      • notion image
    • 종료 조건: step == 0
예제 코드
def binary_search(arr, num): # arr[idx] ≤ num인 가장 큰 idx를 반환
    cur = -1
    step = len(arr)
    
    while step != 0:
        while (cur + step < len(arr) and arr[cur + step] <= num): 
            cur += step
        step //= 2
        
    return cur

arr = [1, 3, 3, 4, 5, 7, 9, 10, 11, 13, 13, 16]
print(binary_search(arr, 10))
 
 
 

4. 실제 문제에서 이분 탐색 알고리즘

  • 이분 탐색 알고리즘은 정렬이 된 상태에서만 사용할 수 있다.
  • 따라서, 정렬이 가능한 상황(또는 정렬이 되어 있는 상태)이라면 이분 탐색을 고려하면 된다.