def searchInsert(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return left
nums = [1, 3, 5, 6]
target = 5
print(searchInsert(nums, target))
Explanation (Python):
The Python solution utilizes a binary search algorithm to find the insertion position of the target element in the sorted array.
Initialize two pointers, left and right, representing the left and right boundaries of the search range.
Iterate until left becomes greater than right.
Find the middle element using (left + right) // 2.
If the middle element is equal to the target, return the index mid.
If the middle element is less than the target, update the left pointer to mid + 1 to search the right half.
If the middle element is greater than the target, update the right pointer to mid - 1 to search the left half.
After the loop ends, return the value of left as the insertion position of the target element.
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
public static void main(String[] args) {
int[] nums = {1, 3, 5, 6};
int target = 5;
Solution solution = new Solution();
System.out.println(solution.searchInsert(nums, target));
}
}
Explanation (Java):
The Java solution follows a similar binary search approach as the Python solution to find the insertion position of the target element in the sorted array.
Initialize two pointers, left and right, representing the left and right boundaries of the search range.
Perform the binary search until left becomes greater than right.
Find the middle element using left + (right - left) / 2.
If the middle element is equal to the target, return the index mid.
If the middle element is less than the target, update the left pointer to mid + 1 to search the right half.
If the middle element is greater than the target, update the right pointer to mid - 1 to search the left half.
After the loop ends, return the value of left as the insertion position of the target element.
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int searchInsert(vector& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
};
int main() {
vector nums = {1, 3, 5, 6};
int target = 5;
Solution solution;
cout << solution.searchInsert(nums, target) << endl;
return 0;
}
Explanation (C++):
The C++ solution also uses a binary search algorithm to find the insertion position of the target element in the sorted array.
Initialize two pointers, left and right, representing the left and right boundaries of the search range.
Perform the binary search until left becomes greater than right.
Find the middle element using left + (right - left) / 2.
If the middle element is equal to the target, return the index mid.
If the middle element is less than the target, update the left pointer to mid + 1 to search the right half.
If the middle element is greater than the target, update the right pointer to mid - 1 to search the left half.
After the loop ends, return the value of left as the insertion position of the target element.