704. 이진 검색

이 문제는 정렬된 정수 배열 nums와 정수 target이 주어졌을 때, target이 배열에 존재하는지 찾고, 존재한다면 그 인덱스를 반환하는 문제입니다. 이 문제를 해결하기 위해 이진 탐색(Binary Search) 알고리즘을 사용합니다. 이진 탐색은 O(log n)의 시간 복잡도를 가지며, 정렬된 배열에서 빠르게 값을 찾을 수 있는 효율적인 방법입니다.

이제 코드의 각 부분을 단계별로 살펴보겠습니다.

1. 알고리즘의 핵심 아이디어

이진 탐색의 핵심은 배열을 반으로 나누어 탐색 범위를 좁혀가는 것입니다. 배열이 정렬되어 있기 때문에, 중간 값을 기준으로 탐색 범위를 절반으로 줄일 수 있습니다. 중간 값이 target보다 작으면 오른쪽 절반만 탐색하고, 크면 왼쪽 절반만 탐색합니다. 이렇게 하면 탐색 범위가 기하급수적으로 줄어들어 빠르게 결과를 찾을 수 있습니다.

2. 코드의 주요 로직 설명

코드는 다음과 같은 주요 부분으로 구성됩니다:

• left와 right 변수를 사용하여 현재 탐색 범위의 시작과 끝을 지정합니다.
• while 루프를 통해 left가 right보다 작거나 같을 동안 탐색을 계속합니다.
• mid는 현재 탐색 범위의 중간 인덱스를 계산합니다.
• nums[mid]가 target과 같은지 비교하여, 같으면 mid를 반환합니다.
• nums[mid]가 target보다 작으면 left를 mid + 1로 업데이트하여 오른쪽 절반을 탐색합니다.
• nums[mid]가 target보다 크면 right를 mid - 1로 업데이트하여 왼쪽 절반을 탐색합니다.
• 탐색 범위를 모두 소진했음에도 target을 찾지 못하면 -1을 반환합니다.

3. 각 단계별 동작 과정

1. 초기화: left는 0, right는 배열의 마지막 인덱스로 초기화합니다.
2. 반복 탐색: while (left <= right) 조건이 참인 동안 반복합니다.
   • mid를 (left + right) / 2의 내림값으로 계산합니다.
   • nums[mid]와 target을 비교합니다.
   • 같다면 mid를 반환하여 탐색을 종료합니다.
   • nums[mid]가 target보다 작다면 left를 mid + 1로 설정하여 오른쪽 절반을 탐색합니다.
   • nums[mid]가 target보다 크다면 right를 mid - 1로 설정하여 왼쪽 절반을 탐색합니다.
3. 결과 반환: 탐색 범위가 소진될 때까지 target을 찾지 못하면 -1을 반환합니다.

4. 핵심 변수들의 역할

• left: 현재 탐색 범위의 시작 인덱스입니다.
• right: 현재 탐색 범위의 끝 인덱스입니다.
• mid: 현재 탐색 범위의 중간 인덱스입니다. 이 값을 기준으로 탐색 범위를 절반으로 줄입니다.

5. 왜 이 방법이 효과적인지

이진 탐색은 정렬된 배열에서 매우 효과적입니다. 매번 탐색 범위를 절반으로 줄이기 때문에, 탐색 속도가 매우 빠릅니다. 예를 들어, 배열의 크기가 1,000,000이라도 최대 20번 이하의 비교만으로 원하는 값을 찾을 수 있습니다. 이러한 효율성 덕분에 O(log n)의 시간 복잡도를 가지며, 문제의 요구사항을 충족합니다.

이렇게 이진 탐색을 통해 문제를 해결할 수 있습니다. 이 알고리즘은 정렬된 배열에서 빠르고 효율적으로 값을 찾을 수 있는 강력한 도구입니다.