Solution For Search Insert Position

The Search Insert Position problem on Leetcode requires to find the index of the target element in a sorted array. If the target element is not present in the array, then find the index where it would be inserted to maintain the sorted order of the array.

Solution:

The simplest approach for solving this problem is to iterate through the sorted array and compare each element to the target element. If the target element is present in the array, return its index. If it is not present in the array, return the index where it would be inserted based on the sorted order of the array.

Let’s look at the implementation of this algorithm.

def searchInsert(nums, target):
for i in range(len(nums)):
if nums[i] == target:
return i
elif nums[i] > target:
return i
return len(nums)

In this solution, we iterate through the array using a for loop. At each index, we check if the element is equal to the target element. If it is equal, we return the index. If the element is greater than the target element, this means that the current index is where the target element would be inserted to maintain the sorted order of the array. Thus, we return the current index. If we reach the end of the array and the target element is not found, this means that the target element would be inserted at the end of the array. Thus, we return the length of the array.

Let’s test our function with some sample inputs.

“`
nums = [1, 3, 5, 6] target = 5
print(searchInsert(nums, target)) # Output: 2

nums = [1, 3, 5, 6] target = 2
print(searchInsert(nums, target)) # Output: 1

nums = [1, 3, 5, 6] target = 7
print(searchInsert(nums, target)) # Output: 4

nums = [1, 3, 5, 6] target = 0
print(searchInsert(nums, target)) # Output: 0
“`

In this way, we can solve the Search Insert Position problem on Leetcode using a simple linear search approach.

Step by Step Implementation For Search Insert Position

public int searchInsert(int[] nums, int target) {
    
    // edge case: empty array
    if (nums.length == 0) {
        return 0;
    }
    
    int left = 0;
    int right = nums.length - 1;
    
    // binary search
    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;
        }
    }
    
    // target not found, left is the index where it should be inserted
    return left;
}

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        if target in nums:
            return nums.index(target)
        else:
            nums.append(target)
            nums.sort()
            return nums.index(target)

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
    // set left pointer to 0 and right pointer to the end of the array
    let left = 0;
    let right = nums.length - 1;
    
    // as long as the left pointer is less than or equal to the right pointer
    while (left <= right) {
        // find the middle index by taking the average of the left and right pointers
        let middle = Math.floor((left + right) / 2);
        
        // if the target is less than the element at the middle index,
        // move the right pointer to the middle - 1
        if (target < nums[middle]) {
            right = middle - 1;
        }
        // if the target is greater than the element at the middle index,
        // move the left pointer to the middle + 1
        else if (target > nums[middle]) {
            left = middle + 1;
        }
        // otherwise, the target is equal to the element at the middle index,
        // so return the middle index
        else {
            return middle;
        }
    }
    
    // if the target is not found in the array,
    // the correct index to insert the target is the left pointer
    return left;
};

class Solution {
public:
    int searchInsert(vector& nums, int target) {
        
        // Base case
        if (nums.size() == 0) {
            return 0;
        }
        
        // Recursive case
        int mid = nums.size() / 2;
        if (target == nums[mid]) {
            return mid;
        } else if (target < nums[mid]) {
            vector left(nums.begin(), nums.begin() + mid);
            return searchInsert(left, target);
        } else {
            vector right(nums.begin() + mid + 1, nums.end());
            return mid + 1 + searchInsert(right, target);
        }
    }
};

public int SearchInsert(int[] nums, int target) {
        
        //check for empty array
        if(nums.Length == 0){
            return 0;
        }
        
        //binary search
        int left = 0;
        int right = nums.Length - 1;
        
        while(left <= right){
            int mid = (left + right) / 2;
            if(nums[mid] == target){
                return mid;
            }
            else if(nums[mid] > target){
                right = mid - 1;
            }
            else{
                left = mid + 1;
            }
        }
        
        //if not found, left is the index where it should be inserted
        return left;
    }