[A100C_day 1] Leetcode 704. Binary Search (java)

 

---

문제 링크

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

LeetCode - The World's Leading Online Programming Learning Platform

 

 

문제 분석

1. 먼저 주어진 nums는 sorted array -> 이제 기본적으로 Binary Search가 가장 먼저 떠올라야 한다. 

2. 1 <= nums.length <= 10^4

• 제곱하더라도 10^8이므로, O(N^2)로 풀어도 풀리긴 할 것 같다!
• (물론 문제의 요구 조건은 O(logN)이지만..!)

3. 유니크한 모든 element들

• 중복에 대한 고려는 할 필요 없을듯!

 

---

Solution 1. Brute Force_Linear Search Algorithm (O(N))

그냥 단순히 선형탐색으로 target과 일치하는 인덱스 찾기.. 

 

class Solution {
    public int search(int[] nums, int target) {
 
        for(int i = 0; i < nums.length; ++i) {
            if(nums[i] == target) return i;
        }    

        return -1;
    }
}

 

성공..이긴하지만..

 

간단한 코드.. 

 

그런데 문제에서 요구하는 O(logN)의 조건을 맞추려면 Binary Search로 접근이 필요하다. 

 

---

Solution 2. Binary Search(O(logN))

정렬된 배열 특성 상 탐색해야할 부분과 탐색하지 않아도 될 부분을 명확히 구분할 수 있는 BS로 접근하기!

 

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

확실히 빠르다!

 

---

Solution 3. Binary Search(O(logN))_Upper Bound

위의 Solution 2번에서.. 굳이 케이스를 세가지로 나눌 필요가 있을까? 

 

target이 존재하는 위치를 찾는 것이 아닌, target이 들어갈 수 있는 위치를 찾는다는 것이 Solution3의 핵심 접근 방식!

 

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

 

prev, next 포인터를 이동시키며 target 값이 있을 범위를 좁혀갔던 Solution2와 달리, Solution3는 target 값보다 큰 첫번째 원소를 찾는다. 

 

간단한 문제라 시간복잡도 측면에서 유의미하게 다른 점은 없지만, 만약 nums의 요소가 유니크하지 않다면 유용하게 쓰일 알고리즘..