[LeetCode] 35. Search Insert Position c++

• 문제

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

 

Input: nums = [1,3,5,6], target = 5
Output: 2

배열 원소 중 target과 같은 값이 있다면 해당 index 구하고,

없다면 오름차순인 배열에 위치시킬 index를 구하는 문제이다.

 

• 문제 해결

이 문제를 해결하기 위해 lower_bound 함수에 대해 알고 있어야 한다.

[c++] lower_bound, upper_bound 함수

 

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        return lower_bound(nums.begin(), nums.end(), target) - nums.begin();
    }
};

 

다른 풀이

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