LeetCode 문제 풀어보기 - 704번 Binary Search

학원 강사님의 강력 추천으로 리트코드에서 코딩테스트 문제를 풀어보기로 했다.

대기업은 영어로 내는곳도 있고 한국 사이트들과 다르게 문제도 새로운것이 지속적으로 올라온다고 하셔서..

대기업을 당장 노려볼수는 없겠지만 그냥 혹해서 풀어봤다.

 

LeetCode - The World's Leading Online Programming Learning Platform

LeetCode - The World's Leading Online Programming Learning Platform

 

이런식으로 2주짜리 알고리즘 코딩테스트 문제들을 깔끔하게 정리해놨길래 공부했던 이진검색 알고리즘 부터 풀어봤다.

확실히 한국 코테 사이트들보다 예쁘긴하다..

 

 

오름차순으로 정렬된 정수형 배열 nums가 주어지고, 정수형 변수인 target을 nums배열에서 찾기위한 함수를 작성해야 한다.

만약 타겟이 존재하면 그 인덱스를 리턴하고, 없다면 -1을 리턴해야 한다.

무조건 O(log n)의 시간 복잡도를 가지는 알고리즘을 사용해야한다.

 

제약 조건들은 배열의 길이와 값의 제한이 있고, nums안에 있는 정수들은 겹치지 않으며

nums배열은 오름차순으로 정렬되어 있다고 한다.

 

class Solution {
public:
    int search(vector<int>& nums, int target) {
        
        int MinIndex = 0;
        int MaxIndex = nums.size()-1;
        int half = 0;
        
        while(MinIndex <= MaxIndex)
        {
            half = (MinIndex+MaxIndex) / 2;
            
            if(nums[half] == target)
                    return half;
            else if(nums[half] < target) 
                MinIndex = half+1;
            else
                MaxIndex = half-1;    

        }
            return -1;
    }
};

 

저번에 배운것을 토대로 코드를 작성했다.

 

최소인덱스와 최대인덱스를 더한 값의 반인 half라는 변수를 이용하여 검색을 하고,

num[하프]의 값보다 타겟이 더 크다면 최소 인덱스를 하프에서 +1해주고

num[하프]의 값보다 타겟이 더 작다면 최대 인덱스를 하프에서 -1 해줬다.

 

타겟이 num[하프]와 같다면 하프를 리턴, 

최소 인덱스가 최대 인덱스보다 커져서 while문을 빠져나오면 -1을 리턴했다.

 

여러번 제출해봤는데 런타임 시간은 할때마다 다르게 나온다.

 

그리고 인텔리전스가 뜨질않아서 작성하는데 맞게 치고 있는건지 헷갈렸다.

인텔리전스를 포함한 프리미엄 기능들을 쓰고싶으면 돈을 내야한다.

 

 

 한달에 35달러 1년으로 하면 159달러..

돈이 없으니 여러번 눌러보는게 더 나을것같다..