Lets Code Everyday - Day 20

Question - 20:

Search Insert Position

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.

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

 First approach:

class Solution {
    public int searchInsert(int[] nums, int target) {
        int toBeInsertedAt=0;
        for(int i=0;i<nums.length;i++){
            if(nums[i]==target)
              return i;
            else if(nums[i]<target)
              toBeInsertedAt=i+1;
        }
        return toBeInsertedAt;
    }
}

Step-by-step implementation:

1. Declare and initialize a variable named toBeInsertedAt to 0. This variable will be used to keep track of the index where the target element needs to be inserted.

2. Iterate through the given array nums using a for loop that runs from i=0 to i<nums. length, i.e., through all the elements of the array.

3. Inside the loop, check if the current element nums[i] is equal to the target element. If so, return the index of that element i. This means that the target element has been found in the given array and its index is returned as output.

4. If the current element is not equal to the target element, check if it is smaller than the target element. If it is, update the value of the variable toBeInsertedAt to i+1. This means that the target element should be inserted after the current element in the array, and the toBeInsertedAt variable keeps track of that index.

5. Once the loop has completed iterating through all the elements of the array, return the value of the toBeInsertedAt variable as output. This means that the target element was not found in the given array, but its index where it should be inserted has been computed and returned.

The algorithmic approach used in the given code is a linear search algorithm. It iterates through the elements of the given sorted integer array nums one by one, comparing each element with the target element. If the target element is found in the array, it returns the index of the element. Otherwise, it keeps track of the index where the target element should be inserted to maintain the sorted order of the array and returns that index at the end.

Time complexity:

• The time complexity of the given code is O(n), where n is the length of the input array nums.

• The for loop iterates through all the elements of the array in the worst-case scenario.

• Each iteration of the loop involves constant time operations.

Space complexity:

• The space complexity of the given code is O(1).

• The space used by the program is constant, regardless of the size of the input array nums.

• The program only uses a few integer variables to store the index and the length of the input array.

Second approach:

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;
    }
}

Step-by-step implementation:

1. Declare and initialize two integer variables named left and right. left is initialized to 0 and right is initialized to the length of the given array nums minus 1. These variables define the range in which the target element can be found or inserted.

2. Use a while loop that runs as long as left is less than or equal to right. This ensures that the range of the array is being searched for the target element.

3. Inside the loop, compute the middle index of the range using the formula mid = left + (right - left) / 2. This formula calculates the middle index of the array by taking the sum of left and right and dividing it by 2. This avoids integer overflow issues that may occur when computing (left + right) / 2.

4. Check if the middle element of the array nums[mid] is equal to the target element. If so, return the index of the middle element mid. This means that the target element has been found in the given array and its index is returned as output.

5. If the middle element is not equal to the target element, check if it is smaller than the target element. If it is, update the value of left to mid + 1. This means that the target element should be searched in the right half of the range of the array.

6. If the middle element is greater than the target element, update the value of right to mid - 1. This means that the target element should be searched in the left half of the range of the array.

7. Once the loop has completed searching through the range of the array, return the value of left as output. This means that the target element was not found in the given array, but its index where it should be inserted has been computed and returned.

The algorithmic approach used in the given code is a binary search algorithm.

The binary search algorithm is an efficient algorithm for searching a sorted array by repeatedly dividing the search interval in half. The idea behind the binary search algorithm is to compare the middle element of the array with the target element being searched. If the middle element is equal to the target element, then the search is complete and the index of the element is returned. If the middle element is smaller than the target element, the search continues in the right half of the array, and if the middle element is greater than the target element, the search continues in the left half of the array.

Conclusion:

The second approach using the binary search algorithm will give better performance than the first approach using a linear search algorithm. This is because the time complexity of the binary search is O(log n) which is faster than the O(n) time complexity of the linear search. The binary search algorithm reduces the search space by half in each iteration, making it faster, especially for larger input arrays.

Thanks for reading...Happy Learning...😁