[24.06.15] 99클럽 코테 스터디 27일차 TIL - 이진 탐색 알고리즘

1. 이진 탐색 알고리즘

이진 탐색(Binary Search)는 정령된 배열 또는 리스트에서 특정 값을 찾기 위해 사용하는 효율적인 알고리즘이다. 이 알고리즘은 탐색 범위를 절반으로 줄여가며 값을 찾기 때문에, 시간 복잠도가 O(logn)으로 매우 빠르다. 

 

1.1 작동방식

1. 초기 값 설정 : 탐색 범위의 시작점인 left와 끝점 right를 설정한다.

2. 중간 값 설정 : mid = (left + right) // 2 로 중간값을 계산한다.

3. 값 비교 : mid 번쨰의 값이 찾고자 하는 값과 같은지 비교한다.

• mid번째 값 == 찾고자 하는 값
  탐색을 종료하고 중간 값을 반환한다
• mid 번째 값 > 찾고자 하는 값
  탐색 범위를 중간 값의 왼쪽 절반으로 줄인다 -> right = mid -1
• mid 번째 값 < 찾고자 하는 값
  탐색 범위를 중간 값의 오른쪽 절반으로 줄인다 -> left = mid + 1

4. 반복 : 위 과정을 찾고자 하는 값을 찾거나 탐색 범위가 없어질 때 까지 반복한다.

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid  # 값을 찾음
        elif arr[mid] < target:
            left = mid + 1  # 오른쪽 절반을 탐색
        else:
            right = mid - 1  # 왼쪽 절반을 탐색
    
    return -1  # 값을 찾지 못함

# 예제 사용
arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
target = 7
result = binary_search(arr, target)
print(result)  # 출력: 3 (배열에서 7의 인덱스)

 

1.2 이진 탐색 적용하기

알고리즘 문제를 풀다보면 이진탐색을 써야할 것 같은데 어떤 조건에 어떻게 써야할지 모르겠을 때가 많았다.

그럴 땐 문제의 성격과 이진 탐색의 특징을 같이 생각해보는 것이 도움이 된다.

이진 탐색은 특정 조건을 만족하는 값의 최댓값이나 최솟값을 찾는 문제에 유용하다.

따라서 문제에서 최솟값 혹은 최댓값을 구하는 부분이 있는지 확인해보자!