정렬 그룹에서 숫자 찾기 - 2분법

면접문제 53-1: 한 숫자가 정렬수 그룹에 나타난 횟수를 통계한다.

해법 1:이분법의 변형

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        if(data.empty())
            return 0;
        int low = 0, high = data.size() - 1;
        int FirstK = BinarySearchFirstK(data, low, high, k);
        int FinalK = BinarySearchFinalK(data, low, high, k);
        
        int TimeOfK = 0;
        if(FirstK > -1 && FinalK > -1) // 
           TimeOfK  = FinalK - FirstK + 1;
        return TimeOfK;
    }
    
     // K , 
    int BinarySearchFirstK(vector<int>& data,int low,int high,int k){
       if(low <= high){
            int mid = (high + low) >> 1;
            if(data[mid] == k){    
                if(mid == 0 || data[mid - 1] != k)
                    return mid;
                else
                    return BinarySearchFirstK(data, low, mid - 1, k);
                //return (mid == 0 || data[mid - 1] != k) ? mid : BinarySearchFirstK(data, low, mid - 1, k);
            }
            if(data[mid] > k)
                return BinarySearchFirstK(data, low, mid - 1, k);
            if(data[mid] < k)
                return BinarySearchFirstK(data, mid + 1,high, k);
        }
        return -1;
    }
    
     // K , 
    int BinarySearchFinalK(vector<int>& data,int low,int high,int k){
       if(low <= high){
            int mid = (high + low) >> 1;
            if(data[mid] == k)    
                return (data.size()-1 == mid || data[mid + 1] != k) ? mid : BinarySearchFinalK(data, mid + 1, high, k);
            if(data[mid] > k)
                return BinarySearchFinalK(data, low, mid - 1, k);
            if(data[mid] < k)
                return BinarySearchFinalK(data, mid + 1,high, k);
        }
        return -1;
    }
};

// 
class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        if(data.empty())
            return 0;
        int low = 0, high = data.size() - 1;
        int FirstK = BinarySearchFirstK(data, low, high, k);
        int FinalK = BinarySearchFinalK(data, low, high, k);
        
        int TimeOfK = 0;
        if(FirstK > -1 && FinalK > -1) // 
           TimeOfK  = FinalK - FirstK + 1;
        return TimeOfK;
    }
    
     // K , 
    int BinarySearchFirstK(vector<int>& data,int low, int high, int k){
       while(low <= high){
            int mid = (high + low) >> 1;
           if(data[mid] == k){    
               if(mid == 0 || data[mid - 1] != k)
                   return mid;
               else
                   high = mid - 1;
           }
            if(data[mid] > k)
                high = mid - 1;
            if(data[mid] < k)
                low = mid + 1;
        }
        return -1;
    }
    
     // K , 
    int BinarySearchFinalK(vector<int>& data,int low,int high,int k){
       while(low <= high){
            int mid = (high + low) >> 1;
            if(data[mid] == k)    
                if(data.size()-1 == mid || data[mid + 1] != k)
                   return mid;
               else
                   low = mid + 1;
            if(data[mid] > k)
                high = mid - 1;
            if(data[mid] < k)
                low = mid + 1;
        }
        return -1;
    }
};

해법 2: STL 2점 찾기 알고리즘

#if 1
//STL:equal_range()  。
class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        auto resultPair = equal_range(data.begin(), data.end(),k);
        return resultPair.second - resultPair.first;
    }
};

#elif 0
//STL:     
class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        return upper_bound(data.begin(), data.end(), k) - lower_bound(data.begin(), data.end(), k);
    }
};
#endif

면접 문제 53 - II.0~n-1에서 빠진 숫자

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        //if(nums.empty()) return -1;  // 
        int low = 0, high = nums.size()-1;
        while(low <= high){
            int mid = (low + high) >> 1;
            if(nums[mid] == mid) // 
                low = mid + 1;
            if(nums[mid] != mid){ // 
                if(mid == 0 || nums[mid - 1 ] == mid - 1)
                    return mid;     // 
                if(nums[mid - 1 ] != mid - 1)
                    high = mid - 1;
            }
        }

    // ， ， 
    if(low == nums.size())
        return nums.size();
    //  ， ， 
    //  0 n-1 （ ）
    return -1;
    }
};