Leetcode-35. 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.

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

The provided solution aims to find the index where a target value should be inserted into a sorted array of distinct integers, while maintaining the array's sorted order. The goal is to achieve a solution with a time complexity of O(log n), which suggests the use of a binary search algorithm, but the provided code implements a linear approach instead.

The solution begins by initializing a variable `n` to hold the size of the input array `nums`. The variable `count` is also initialized to 0, which will serve as the index to insert the target value. The loop iterates through the array from the start to the end, comparing each element of the array with the target value. If the current element is smaller than the target, it increments the `count` variable, meaning that the target could be inserted after this element. If an element greater than or equal to the target is found, the function immediately returns the current value of `count`, which represents the index at which the target should be inserted.

However, if the loop completes without finding a suitable position (i.e., if the target is larger than all the elements in the array), the function checks if the target is greater than the last element of the array. If this condition is true, it returns the value `n`, which is the index just beyond the last element, effectively placing the target at the end of the array.

While this solution correctly finds the index where the target should be inserted, it does not achieve the required O(log n) runtime complexity. The approach implemented here is linear, as it uses a simple `for` loop to iterate through all the elements of the array. A more optimal approach to solve this problem in O(log n) time would involve using binary search, which efficiently narrows down the search space by repeatedly halving the array.

For example, for an input array `nums = [1, 3, 5, 6]` and `target = 5`, the function will return `2`, as the target is found at index 2. For a `target = 2`, the function will return `1`, indicating that the target should be inserted at index 1. Similarly, for a `target = 7`, the function will return `4`, indicating that the target should be inserted at the end of the array.

CODE:

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

                }
            else
                return count;
            }
        if(target>nums[n-1]){
            return n;
            }
         return 0;
        }          
};