(Leet Code c++)Search Insert Position

35. Search Insert Position

 

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.

 

Example 1:

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

Example 2:

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

Example 3:

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

Example 4:

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

Example 5:

Input: nums = [1], target = 0 Output: 0

 

Constraints:

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums contains distinct values sorted in ascending order.
• -104 <= target <= 104

이분 탐색을 통해 nums 벡터 안에서 target 숫자의 인덱스를 찾는다.

만약 nums 안에 target이 없으면 target이 들어갈 위치를 리턴해주면 된다.

 

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