Search Insert Position

#35.Search Insert Position

Problem statement

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

Explanation

給定一個排序陣列和一個目標值，其中陣列內的元素不重複，如果在陣列中找到目標值則返回其索引，若陣列內不存在目標值，則返回應當插入位置的索引

限制解法的時間複雜度為 O(log n)

Solution

由題目給的是已排序陣列，沒有太多想法，直接使用二分搜尋法來解

public int SearchInsert(int[] nums, int target)
{
    int left = 0, right = nums.Length - 1, mid;

    while (left <= right)
    {
        mid = (left + right) / 2;

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

    return left;
}

Reference

LeetCode Solution

GitHub Repository

Thanks for reading the article 🌷 🌻 🌼

If you like it, please don't hesitate to click heart button ❤️
or click like on my Leetcode solution
or follow my GitHub ⭐ I'd appreciate it.