[LeetCode] Binary Search

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

Binary Search - LeetCode

 

앞선 포스트 'LeetCode Plan'에서 소개한 Blind 75에 속하는 문제는 아니고 업데이트 버전인 Grind 75에 속하는 문제입니다. Binary Search의 가장 기본적인 예제로 아주 쉬운 문제이지만 다음 두 가지 방식으로 풀어보았습니다.

 

03/06

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if(binary_search(nums.begin(), nums.end(), target)){
            return lower_bound(nums.begin(),nums.end(), target) - nums.begin();
        }
        else{
            return -1;
        }
    }
};

 

C++ STL <algorithm> header에 포함되어 있는 함수들을 이용해 간단하게 풀어보았습니다. binary_search 결과 배열 내에 target이 존재할 경우 해당 index를 찾아 return하고, 그렇지 않을 경우 -1을 return합니다.

 

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size()-1;
        int mid;

        while(left <= right){
            mid = (left + right) >> 1;
            if(nums[mid] > target){
                right = mid-1;
            }
            else if(nums[mid] < target){
                left = mid+1;
            }
            else{
                return mid;
            }
        }
        return -1;    
    }
};

 

이번에는 binary search를 직접 구현하여 풀어봤습니다. Binary search 정도는 직접 구현할 수 있어야 합니다. Up & down 게임을 생각하면 이해하는 데 도움이 될 것 같습니다.

 

 

다만 직접 구현할 경우 Runtime이 상대적으로 느리게 나오는데, 시간복잡도는 동일하게 O(logN)으로 문제될 것은 없습니다.