[LeetCode - C] 35. Search Insert Position

Search Insert Position - LeetCode

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

 

Constraints:

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

---

Solution 1

 

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

 

이 항목 때문에 어떻게 풀지 고민하다가

 

이분 탐색 하면 될 거 같아서

 

전에 했던 나무 자르기 참고해서 해결했다.

단계별로 풀어보기(이분 탐색 - 나무 자르기)

int searchInsert(int* nums, int numsSize, int target)
{
    int max;
    int mid;
    int min;
    
    max = numsSize;
    min = 0;
    if (nums[0] > target)
        return (0);
    if (nums[numsSize - 1] < target)
        return (numsSize);
    while (min <= max)
    {
        mid = (max + min) / 2;
        if (nums[mid] < target)
            min = mid + 1;
        else
            max = mid - 1;
    }
    return (min);
}

int searchInsert(int* nums, int numsSize, int target)
{
    int max;
    int mid;
    int min;
    
    max = numsSize - 1;
    min = 0;
    while (min <= max)
    {
        mid = (max + min) / 2;
        if (nums[mid] == target)
            return (mid);
        else if (nums[mid] < target)
            min = mid + 1;
        else
            max = mid - 1;
    }
    return (min);
}