In the Leetcode Search Insert Position problem solution 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
Solution in C Programming
int searchInsert(int* nums, int numsSize, int target){
int i = 0;
while(numsSize--) {
if(nums[i] == target || nums[i] > target) {
return i;
}
i++;
}
return i;
}Solution in C++ Programming
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
for (int i = 0; i < nums.size(); i ++)
{
if (nums[i] >= target)
return i;
}
return nums.size();
}
};Solution in Java Programming
class Solution {
public int searchInsert(int[] nums, int target) {
return binSearch(0, nums.length, nums, target);
}
public int binSearch(int start, int end, int[] nums, int target){
int mid = start + (end - start) / 2;
// case when the target isn't in the array, the target would go in the start position
if (start >= end){
return start;
}
// target found, return the index
if (nums[mid] == target){
return mid;
}
int g = -1;
// perform binary search in the corresponding subsection
if (nums[mid] > target){
g = binSearch(start, mid, nums, target);
} else{
g = binSearch(mid + 1, end, nums, target);
}
if (g != -1){
return g;
}
return -1;
}
}Solution in Python Programming
class Solution(object):
def searchInsert(self, nums, target):
left, right, mid = 0, len(nums)-1, 0
while(left<=right):
mid = left + (right-left)//2
if(nums[mid]==target):
return mid
elif(nums[mid]<target):
left = mid+1
else:
right = mid -1
return leftSolution in C# Programming
public 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)
{
right = mid;
}
else if (nums[mid] < target)
{
left = mid + 1;
}
else {
return mid;
}
}
if (target > nums[nums.Length - 1]) return nums.Length;
return left;
}
}Also read,