🚀 이진 탐색 (Binary Search)

정렬된 배열에서 특정 값을 빠르게 찾는 알고리즘으로, 탐색 범위를 절반씩 줄여가며 원하는 값을 찾는다.

📌 이진 탐색 개념

• 정렬된 배열에서만 사용 가능

• 탐색 범위를 절반씩 줄여 빠르게 값을 찾음

• 시간 복잡도: O(log N) → 매우 효율적!

조건 : 데이터가 정렬되어 있어야함

🛠 탐색 과정

1. 좌측 인덱스 (left) 설정 / 초기 설정은 array의 시작 (0 index)

2. 우측 인덱스 (right) 설정 / 초기 설정은 array의 마지막 index

3. 중간 인덱스 (min) 설정 / (left + right) / 2 로 갱신

범위의 중간 값을 확인하여 타겟 값보다 크거나 작으면 right 혹은 left 값을 mid값으로 설정한다.

🖥️ 예시 : 34를 찾으려고 할 때

**1. 전체 범위에서 중간값을 확인한다. **

이 때, 찾고자 하는 값은 34이고 mid값은 27이므로 현재의 중간값은 타겟값보다 작다.

그러므로 범위를 오른쪽으로 좁혀야한다.

left = mid + 1, mid = (left + right) / 2로 갱신한다.

2. 다음 중간값은 38이다. 타겟 값은 34이고 중간값보다 작으므로 범위를 왼쪽으로 좁힌다. right = mid - 1, mid = (left + right) / 2로 갱신한다.

3. 중간값은 30이므로 오른쪽으로 범위를 좁힌다.

4. 현재 left, mid, right가 같은 인덱스로 설정되었다. 현재 중간값은 타겟값과 일치하기에 타겟값이 몇 번 인덱스에 위치하는지 확인하였다.

이처럼 이진탐색은 정렬된 배열에서 적은 계산으로 빠르게 타겟 인덱스를 찾아낼 수 있는데,

여기서 right = mid - 1 혹은 left = mid + 1처럼 새로운 범위를 기존 mid 인덱스 보다 1 더 높거나 낮은 값으로 설정하는 특징 덕분에 찾으려는 타겟 값이 배열에 존재하지 않는 상황에도 사용할 수 있다. (타겟 값이 배열에서 몇 번째로 큰지 확인하고 변경하는 상황 등)

이 때, 반복문의 조건을 left <= right로 설정하면 배열에 타겟값과 같은 값이 존재하지 않더라도 배열에 몇 번째로 큰 값이 되는지 확인할 수 있다.

예를 들어 위와같은 상황일 때 타겟 값이 36이라고 해보자.

중간값은 34이지만 타겟 값은 36이므로 탐색 범위를 오른쪽으로 좁혀야 한다.

현재 left, mid, right가 같은 인덱스인 상황에서 left = mid + 1로 갱신하게 되면 left가 right보다 오른쪽에 존재하는 상황이 된다.

이 때 반복문의 조건 left <= right 에서 false를 리턴하고 이는 배열에서 찾을 수 있는 타겟 값에 가장 가까운 인덱스에 도착했다는 뜻이 된다.

고로 현재의 left인덱스 (현재 값 : 38) 부분에 36을 할당할 수 있다.

⏰ 시간복잡도

for문을 사용해서 배열의 요소를 비교할 때 걸리는 시간과 이진탐색을 비교해보자.

이 때, 최악의 상황을 고려하여 배열 마지막 인덱스에 타겟 값이 존재한다.

선형 탐색은 배열의 길이만큼 연산이 필요하지만 이진탐색은 O(log N)의 시간복잡도를 가진다.

배열을 절반으로 쪼개는 연산을 반복하기 때문에

배열의 길이 N을 2로 무한히 나누어 1이 될 때 까지 반복하여 log N의 시간복잡도를 가진다.

코드 (Java)

for(int i=0;i<dp.length;i++){
            for(int j=0;j<i;j++){
                if(arr[j]<arr[i]){
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }