LeetCode 704(Binary Search, java)

0. 문제

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

Binary Search - LeetCode

 

1. 문제 설명

- 문제에서 정수로 이루어진 배열(nums)과 찾는 수(target)가 주어진다.

- O(log n)의 시간 복잡도로 탐색을 수행하여 배열에 있는 target의 존재 유무를 파악하는 것이 문제의 핵심이다. 

 

2. 문제 해설

a) 첫 번째 접근

- O(log n)의 시간 복잡도로 탐색을 하기 위해서는 이진 탐색을 사용해야 한다.

- 문제에서 주어진 배열(nums)은 오름차순으로 정렬되어 있다.

- 이를 이용하여 배열의 중간 index를 시작으로 탐색을 수행하면 된다. 

 

b) 두 번째 접근

- 배열의 중간 index를 기준으로 target이 비교 숫자보다 작다면 좌측으로 탐색을 수행한다.

- 배열의 중간 index를 기준으로 target이 비교 숫자보다 크다면 좌측 탐색을 수행한다. 

 

c) 세 번째 접근

- 탐색을 계속 수행하는데도 불구하고 target을 만나지 못한다면 -1을 반환한다.

- 그렇다면 target이 존재하지 않는다는 판단은 무슨 기준으로 해야 할까?

  → 좌측 탐색을 수행하는 도중에 target보다 작은 숫자를 만난다면 target은 존재하지 않는 것이다.

  → 반대로 우측 탐색을 수행하는 도중에 target보다 큰 숫자를 만난다면 target은 존재하지 않는 것이다.

 

- 그러나 이 방식은 효율적이지 않다. 너무 많은 if문을 필요로 하기 때문이다.

- 더불어, 배열을 탐색하는 과정에서 사용하는 반복문의 종료 시점이 명확하지 않다.

- 아래의 코드를 보면서 이해해보자. 

 

d) 네 번째 접근

- 가장 효율적인 방법은 이진 탐색을 진행하면서 two pointers 방식을 사용하는 것이다.

- 여기서 two pointer란, 배열의 처음(= start)과 마지막(= end) index를 사용하여 탐색하는 방식을 의미한다.

 

- 이 두 개의 포인터를 이용하여 중간(=mid) index를 계산한다.

- target보다 큰 수를 만난다면 end를 mid - 1로 변경하고 mid를 다시 계산한다.

- target보다 작은 수를 만난다면 start를 mid + 1로 변경하고 mid를 다시 계산한다.

- 이 과정에서 항상 start는 end보다 작거나 같아야 한다.

 

- 이처럼 two pointer를 이용한 방식은 배열 탐색 시 사용하는 반복문의 종료 시점을 명확하게 만든다. 

- 아래의 코드를 보면서 이해해보자. 

 

3. 정답 코드

a) 해결방법 1 - 이진 탐색만 사용

class Solution {
    public int search(int[] nums, int target) {
        
        int mid = 0;
        
        if(nums.length >= 2) {
            mid = nums.length / 2;
        }
        else {mid = 0;}
        
        while(mid >= 0 && mid < nums.length) {
            if(nums[mid] == target) {return mid;}
            
            else if(nums[mid] > target) {
                mid--;
                if(mid < 0 || nums[mid] < target) {
                    return -1;
                }
            }
            else {
                mid++;
                if(mid >= nums.length || nums[mid] > target) {
                    return -1;
                }
            }
        }
        return -1;
    }
}

 

b) 해결방법 2 - 이진 탐색 + two pointers

class Solution {
    public int search(int[] nums, int target) {
        
        int end = nums.length - 1;
        int start = 0;
        int mid = 0;
        
        while(start <= end) {
            mid = (start + end) / 2; 
    
            if(nums[mid] == target) return mid;        
            else if(nums[mid] < target) start = mid + 1;
            else end = mid - 1;
        }
        return -1;
    }
}