Leet code 35 Java Solution: Search insert position

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.

Solution:-

Summary of the problem:-

Here we have to search in the given sorted array that if the given number is present or not. If the given number is present, then we have to print out the position of that number and if that number is not present, then we have to return the appropriate position of that number in that sorted array.

Approach:-

1. Here we will define two variables. Start position and the end position.
2. Then we will search that sorted array. We will perform a binary search here for that given number.
3. If the number is present, then the position of that number will be returned, else we will return the appropriate location where the number should be present.

Flow chart:-

Code in Java :-

class Solution {
    public int searchInsert(int[] nums, int target) {
        
        int n = nums.length;
        
        int start = 0;
        
        int end = n-1 ;
        
        
        while(start <= end) 
        {
            int mid = (start+end)/2 ;
            
            if(nums[mid] == target)
            {
                return mid ;
            }
            
            else if 
                
                (nums[mid] < target)
                
            {
                start = mid +1;
            }
            
            else {
                end = mid -1 ;
            }
            
        }
        return end+1;
        
        
    }
}

Time Complexity :- As binary search used. So the time complexity is O(n).

Space Complexity :- Here the space complexity is O(1). As here only one data structure is used.