Description:
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.
Examples:
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: 4Solution in Python:
To solve this problem with O (log n) runtime complexity, we need to use a binary search algorithm. Here is the implementation in Python with detailed comments explaining each step.
Python
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
# Initialize the left and right pointers for the binary search
left, right = 0, len(nums) - 1
# Perform binary search
while left <= right:
# Calculate the middle index
mid = (left + right) // 2
# If the target is found, return the middle index
if nums[mid] == target:
return mid
# If the target is less than the middle element, search the left half
elif nums[mid] > target:
right = mid - 1
# If the target is greater than the middle element, search the right half
else:
left = mid + 1
# If the target is not found, 'left' will be the insertion point
return left
# Example usage
solution = Solution()
print(solution.searchInsert([1, 3, 5, 6], 5)) # Output: 2
print(solution.searchInsert([1, 3, 5, 6], 2)) # Output: 1
print(solution.searchInsert([1, 3, 5, 6], 7)) # Output: 4Explanation:
- Initialization:
- We initialize two pointers,
leftandright, to the start and end of the list respectively. leftstarts at index0, andrightstarts at the last index of the list (len(nums) - 1).
- We initialize two pointers,
- Binary Search Loop:
- We enter a loop that continues until
leftexceedsright. - Inside the loop, we calculate the middle index
midusing integer division to ensure we get an integer result.
- We enter a loop that continues until
- Comparison:
- We compare the element at the middle index
nums[mid]with thetarget. - If
nums[mid]equals thetarget, we returnmidbecause we’ve found the target. - If
nums[mid]is greater than thetarget, we updaterighttomid - 1to search the left half of the list. - If
nums[mid]is less than thetarget, we updatelefttomid + 1to search the right half of the list.
- We compare the element at the middle index
- Insertion Point:
- If the loop exits without finding the target,
leftwill be the index where the target should be inserted to maintain sorted order. - We return
leftas the insertion point.
- If the loop exits without finding the target,
Solution in Javascript:
JavaScript
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var searchInsert = function(nums, target) {
// Initialize the left and right pointers for the binary search
let left = 0;
let right = nums.length - 1;
// Perform binary search
while (left <= right) {
// Calculate the middle index
let mid = Math.floor((left + right) / 2);
// If the target is found, return the middle index
if (nums[mid] === target) {
return mid;
}
// If the target is less than the middle element, search the left half
else if (nums[mid] > target) {
right = mid - 1;
}
// If the target is greater than the middle element, search the right half
else {
left = mid + 1;
}
}
// If the target is not found, 'left' will be the insertion point
return left;
};
// Example usage
console.log(searchInsert([1, 3, 5, 6], 5)); // Output: 2
console.log(searchInsert([1, 3, 5, 6], 2)); // Output: 1
console.log(searchInsert([1, 3, 5, 6], 7)); // Output: 4
console.log(searchInsert([1, 3, 5, 6], 0)); // Output: 0Solution in Java:
Java
class Solution {
public int searchInsert(int[] nums, int target) {
// Initialize the left and right pointers for binary search
int left = 0;
int right = nums.length - 1;
// Perform binary search
while (left <= right) {
// Calculate the middle index
int mid = left + (right - left) / 2;
// If the target is found at mid, return mid
if (nums[mid] == target) {
return mid;
}
// If target is less than the middle element, search in the left half
else if (nums[mid] > target) {
right = mid - 1;
}
// If target is greater than the middle element, search in the right half
else {
left = mid + 1;
}
}
// If the loop exits without finding the target, 'left' will be the insertion point
return left;
}
// Example usage
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums1 = {1, 3, 5, 6};
int target1 = 5;
System.out.println(solution.searchInsert(nums1, target1)); // Output: 2
int[] nums2 = {1, 3, 5, 6};
int target2 = 2;
System.out.println(solution.searchInsert(nums2, target2)); // Output: 1
int[] nums3 = {1, 3, 5, 6};
int target3 = 7;
System.out.println(solution.searchInsert(nums3, target3)); // Output: 4
}
}Solution in C#:
C#
public class Solution {
public int SearchInsert(int[] nums, int target) {
// Initialize the left and right pointers for binary search
int left = 0;
int right = nums.Length - 1;
// Perform binary search
while (left <= right) {
// Calculate the middle index
int mid = left + (right - left) / 2;
// If the target is found at mid, return mid
if (nums[mid] == target) {
return mid;
}
// If target is less than the middle element, search in the left half
else if (nums[mid] > target) {
right = mid - 1;
}
// If target is greater than the middle element, search in the right half
else {
left = mid + 1;
}
}
// If the loop exits without finding the target, 'left' will be the insertion point
return left;
}
}