Search Insert Position in Java
The "search insert position" refers to finding the index at which a given target element should be inserted into a sorted array to maintain its sorted order. The function should return its index if the target element is already present in the array. If the target is absent, it should return the index at which it would be inserted while maintaining the sorted order.
Example 1:
Input: num = [1,3,5,6], target = 5
Output: 2
Explanation:
For example, given a sorted array [1, 3, 5, 6] and a target element 5, the index of 5 is 2 because it is at the third position in the array (0-based indexing).
Example 2:
Input: nums = [1,3,5,6], target = 2
Output: 1
Explanation:
If the target were 2, the function would return 1 because 2 should be inserted at the second position to keep the array sorted.
Example 3:
Input: nums = [1,3,5,6], target = 7
Output: 4
Explanation:
If the target were 7, the function would return 4 because 7 should be inserted at the fifth position to keep the array sorted.
Approach:
Step 1: Initialize two pointers, low and high, to the array's start and end, respectively.
Step 2: Enter a while loop that continues as long as low is less than or equal to high.
Step 3: Inside the loop, calculate the middle index mid as the average of low and high.
Step 4: Check if the element at index mid equals the target. If it is, return mid as the target is found.
Step 5: If the element at index mid is less than the target, update low to mid + 1 to search in the right half of the array.
Step 6: If the element at index mid is greater than the target, update high to mid-1 to search in the left half of the array.
Step 7: Repeat steps 3-6 until the low pointer exceeds the high pointer.
Step 8: Return the low pointer as the insert position if the target is not found.
Let us try to understand using the following Java program
Filename: SearchInsertPosition.java
public class SearchInsertPosition {
public static int searchInsert(int[] nums, int target) {
int low = 0;
int high = nums.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (nums[mid] == target) {
return mid; // Element found at mid index
} else if (nums[mid] < target) {
low = mid + 1; // Search in the right half
} else {
high = mid - 1; // Search in the left half
}
}
return low; // Target not found, return the insert position
}
public static void main(String[] args) {
int[] nums = {1, 3, 5, 6};
int target = 5;
int result = searchInsert(nums, target);
System.out.println("Insert position: " + result);
}
}
Output:
Insert position: 2
Complexity analysis:
The time complexity of the provided binary search implementation in the searchInsert method is O(log N), where N is the number of elements in the input array nums.