23.04.01. 풀었던 문제들

Leetcode 704. Binary Search

 이진 탐색으로 풀면 되는 간단한 문제.

// Runtime 42 ms Beats 45.34%
// Memory 27.6 MB Beats 18.24%

class Solution {
public:
    int search(vector<int>& v, int input) {
        int start = 0, end = v.size()-1, mid;
    while(start <= end){
        mid = (start + end) / 2;
        if(v[mid] < input){
            start = mid + 1;
        } else if(v[mid] == input){
            return mid; // found
        } else{
            end = mid - 1;
        }
    }
    return -1; // not found
    }
};

 

시간복잡도

 O(logn)

 

공간복잡도

 추가 공간을 사용하지 않으므로 O(1)