35. Search Insert Position

普通にサーチしたら下記の結果となったが、O(log n)で作れとあった。これだとO(n)である。バイナリサーチならば条件を満たすらしいので下に作成。

普通の

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int len = nums.size();
        if(len == 0){
            return 0;
        }
        
        for(int i=0; len >i; i++){
            if(nums[i] == target)
            {
                return i;
            }
            else if(nums[i] > target){
                return i;                
            }
        }
        return len;
    }
};

バイナリサーチ

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int len = nums.size();
        if(len == 0){
            return 0;
        }
        
        int low = 0;
        int hi = len -1;
        int mid;
        while(low <= hi){
            mid = (low + hi) / 2;
            if(nums[mid] == target)
            {
                return mid;
            }else if(nums[mid] < target)
            {
                low = mid +1;
            }
            else{
                hi = mid -1;
            }
        }
        return low;
    }
};