search insert position

 35. Search Insert Position

Easy

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

myCODE.py:

class Solution: def searchInsert(self, nums: List[int], target: int) -> int: nums.append(target) nums[:]=list(set(nums)) nums.sort() print(nums) for x,y in enumerate(nums): if y==target: return x

Other Code:

Linear Search

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        if not nums:
            return 0
        
        for i, num in enumerate(nums):
            if num >= target:
                return i
        
        return len(nums)

Binary Search By Hand

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        low, high = 0, len(nums)
        while low < high:
            mid = (low + high) // 2
            if target > nums[mid]:
                low = mid + 1
            else:
                high = mid
        return low

MyCode.cpp:

class Solution { public: int searchInsert(vector<int>& nums, int target) { int i=0; for ( i;i<nums.size();i++){ if (nums[i]>=target) return i; } return i; } };

Other:

Approach

BINARY SEARCH

Complexity

Time complexity:O(logn)

Space complexity:O(1)

Code

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int st=0; int end=nums.size()-1;
        int ans=0;
        while(st<=end){
            int mid=(st+end)/2;
            if(nums[mid]<target){
                st=ans=mid+1;
                
            }
            else if(nums[mid]>target){
                end=mid-1;
            }else{
                return mid;
            }
        }
        return ans;
    }
};