DEV Community ๐Ÿ‘ฉโ€๐Ÿ’ป๐Ÿ‘จโ€๐Ÿ’ป

Cover image for Search Insert Position
FakeStandard
FakeStandard

Posted on

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
Enter fullscreen mode Exit fullscreen mode

Example 2

Input: nums = [1,3,5,6], target = 2
Output: 1
Enter fullscreen mode Exit fullscreen mode

Example 3

Input: nums = [1,3,5,6], target = 7
Output: 4
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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 โญ
or buy me a coffee โฌ‡๏ธ I'd appreciate it.

Buy-me-a-coffee


Top comments (0)

Here is a post you might want to check out:

Regex for lazy developers

regex for lazy devs

Sorry for the callout ๐Ÿ˜†