Binary Search

문제

오름차순으로 정렬된 정수 배열 nums와 찾고자 하는 목표값 target이 주어집니다. 배열에서 target을 검색하여 그 인덱스를 반환하는 프로그램을 작성하는 문제입니다. 만약 배열에 target이 존재하지 않는다면 -1을 반환해야 합니다. 알고리즘은 반드시 O(log N)의 시간 복잡도로 작성되어야 합니다.

• 입력: 오름차순 정렬된 정수 배열 nums (1 <= nums.length <= 10^4), 찾을 정수 target
• 출력: target의 인덱스 (존재하지 않으면 -1)

링크: https://leetcode.com/problems/binary-search

풀이: 정렬된 배열에서의 O(log N) 탐색

배열이 이미 오름차순으로 정렬되어 있다는 조건을 활용하여, 탐색 범위를 매번 절반으로 줄여나가는 이진 탐색(Binary Search)의 가장 정석적이고 완벽한 구현입니다.

• 탐색 범위 초기화: 탐색의 시작점 s를 배열의 첫 인덱스(0)로, 끝점 e를 마지막 인덱스(nums.length - 1)로 설정합니다.
• 반복 조건: s <= e를 유지하는 동안 탐색을 반복합니다. 두 포인터가 교차하는 순간은 배열 전체를 확인했음에도 찾는 값이 없음을 의미합니다.
• 중간점 검사 및 범위 축소:
  • 중간 인덱스 m = (s + e) / 2를 계산하여 중간값 nums[m]과 target을 비교합니다.
  • nums[m] == target: 값을 찾았으므로 즉시 인덱스 m을 반환합니다.
  • nums[m] < target: 중간값보다 타겟이 크므로, 타겟은 무조건 중간점의 오른쪽에 존재합니다. 따라서 시작점을 m + 1로 옮겨 오른쪽 절반만 탐색합니다.
  • nums[m] > target: 타겟이 중간값보다 작으므로, 타겟은 무조건 중간점의 왼쪽에 존재합니다. 따라서 끝점을 m - 1로 옮겨 왼쪽 절반만 탐색합니다.
• 탐색 실패: 반복문을 무사히 빠져나왔다면 값이 없는 것이므로 -1을 반환합니다.

코드

class Solution {
    public int search(int[] nums, int target) {
        int s = 0;
        int e = nums.length - 1;

        while(s <= e) {
            int m = (s + e) / 2;
            if (nums[m] == target) {
                return m;
            } else if (nums[m] < target) {
                s = m + 1;
            } else {
                e = m - 1;
            }
        }

        return  -1;
    }
}

알고리즘 분류

이진 탐색 (Binary Search)