[ALGORITHM] 07. O(log n)

O(log n)은 이진 로그(logarithmic) 시간 복잡도를 가지는 알고리즘을 나타낸다.

이는 입력 크기 n에 대해 로그의 형태로 실행 시간이 증가하는 알고리즘을 의미한다.

주로 이진 탐색과 같은 분할 정복 알고리즘에서 발생하며, 큰 데이터셋에서 효과적으로 동작하는 특성 덕에

탐색이나 정렬과 같은 문제에서 자주 사용된다.

 

int binarySearch(int arr[], int left, int right, int target) {

    while (left <= right) {
    
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
        
            return mid;  // 요소를 찾았을 경우 인덱스 반환
        }

        if (arr[mid] < target) {
        
            left = mid + 1;  // 중간 값이 타겟보다 작으면 오른쪽 부분을 탐색
            
        } else {
        
            right = mid - 1;  // 중간 값이 타겟보다 크면 왼쪽 부분을 탐색
        }
    }

    return -1;  // 요소를 찾지 못한 경우
}