LeetCode #35 Cover Photo - searching

LeetCode #35 Search Insert Position Solution & Explanation

Klook.com
Post Views: 674

LeetCode Problem

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.

LeetCode #35 Examples
LeetCode #35 Constraints

Solution

This question seems simple, we can easily finish it with an iteration.

And that’s is wrong!

C# Solution

❌First try

public class Solution {
    public int SearchInsert(int[] nums, int target) {
        for(int i=0;i<=nums.Length-1;i++)
        {
            if(target<=nums[i])
            {
              return i;
            }
        }
        return nums.Length;
    }
}

Time Complexity : O(n) ➡ but we need to reduce it to O(log n)

Solution1 – Binary Search

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

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

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

        return left;
    }
}

Time Complexity : O(log n)

Because the array is already sorted, so we can use 【Binary Search】 to easily find the insert position.

Java Solution

Solution1

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

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

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

        return left;
    }
}

Runtime : 0ms、0ms、0ms

Python3 Solution

Solution1

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1

        while left <= right:
            mid = left + (right - left) // 2

            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1

        return left

Runtime : 65ms、72ms、68ms

JavaScript Solution

Solution1

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
    let left = 0;
    let right = nums.length - 1;

    while (left <= right) {
        let mid = Math.floor(left + (right - left) / 2);

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

    return left;
};

Conclusion

🧡If my solution helps, that is my honor!

✅If you got any problem about the explanation or you need other programming language solution, please feel free to let me know (either leave a comment or contact me by Messenger is ok!)

Cover Photo – Photo by Mick Haupt on Unsplash

The problem link : Search Insert Position – LeetCode

See an advanced version of this question : LeetCode #34 Find First and Last Position of Element in Sorted Array Solution & Explanation

Latest Post

Related Posts

Leave a Reply

Your email address will not be published. Required fields are marked *