Brooke

一、題目

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

 

二、程式作法

/*寫法一*/
public class Solution
{
    public int SearchInsert(int[] nums, int target)
    {
        int left = 0;
        int right = nums.Length - 1;
        int pivot = 0;

        while (left < right)
        {
            pivot = left + (right - left) / 2;
            if (nums[pivot] == target)
                return pivot;

            if (nums[pivot] > target)
                right = pivot - 1;
            else
                left = pivot + 1;
        }

        pivot = left + (right - left) / 2;
        if (nums[pivot] == target)
            return pivot;

        if (nums[pivot] > target)
            return pivot;
        else
            return pivot + 1;
    }
}

/*寫法二*/
/*
public class Solution
{
    public int SearchInsert(int[] nums, int target)
    {
        int lowBound = 0;
        int upBound = nums.Length - 1;
        int pivot = 0;
        string direction = "";

        while (lowBound <= upBound)
        {
            pivot = lowBound + (upBound - lowBound) / 2;

            if (target == nums[pivot]) return pivot;

            if (target >= nums[pivot])
            {
                lowBound = pivot + 1;
                direction = "going down";
            }
            else
            {
                upBound = pivot - 1;
                direction = "going up";
            }
        }

        if (direction == "going down") return pivot + 1;
        else return pivot;
    }
}
*/

 

三、思路筆記

使用二分搜尋法來做。