35. Search Insert Position

Question Type: Easy
Liked by :14.6K
Disliked by: 630

Companies asked this Question:

Company name : No of Times
Amazon 4
Google 2
Apple 8
Microsoft 5
Adobe 4
Yahoo 2
Bloomberg 2
Facebook 7
VMware 5
Uber 4
LinkedIn 2
TikTok 2
tcs 2

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

Approach:

Initialize Pointers:
Initialize two pointers, start and end, to represent the search range within the sorted array.start initially points to the first element (index 0), and end points to the last element (index nums.length - 1).

Binary Search Loop:
Enter a while loop that continues as long as start is less than or equal to end.

Calculate Middle Index:
Calculate the middle index mid as start + (end - start) / 2. This ensures that the middle index is always rounded down to an integer, avoiding potential overflow issues.

Compare with Target:
Check if the element at index mid is equal to the target value.
If they are equal, return mid as the index where the target is found.

Adjust Pointers:
If the element at index mid is greater than the target, update end to mid - 1 to search in the left half of the current range.
If the element at index mid is less than the target, update start to mid + 1 to search in the right half of the current range.

Return Insertion Point:
If the while loop exits without finding the target (i.e., start becomes greater than end), return start as the index where the target should be inserted.

Code(in Java):

class Solution {
    public int searchInsert(int[] nums, int target) {
         int start = 0;
         int end = nums.length - 1;

         while(start <= end){
             int mid = start +(end - start) / 2;
             if(nums[mid] == target) return mid;
             if(nums[mid] > target) end = mid - 1;
             if(nums[mid] < target) start = mid + 1;
         }
         return start;
    }
}

Time Complexity Analysis:
Binary search has a time complexity of O(log n), where n is the number of elements in the array. This approach ensures that the search is performed efficiently.

Happy coding,
shiva