Algorithm
Problem - Search Insert Position
URL - https://leetcode.com/problems/search-insert-position/
Level - Beginner
Details:
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] <= 104numscontains distinct values sorted in ascending order.-104 <= target <= 104
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
var searchInsert = function(nums, target) {
for (let i = 0; i < nums.length; i++) {
const num = nums[i];
if (num == target || num > target) {
return parseInt(i);
} else if (typeof nums[i + 1] !== "undefined" && nums[i + 1] > target) {
return parseInt(i + 1);
}
}
return nums.length;
};
Input
2
Output
#2 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
int searchInsert(int A[], int n, int target) {
int l, r, m;
l = 0;
r = n - 1;
while (l < = r) {
m = (l + r) / 2;
if (A[m] == target) {
return m;
}
else if (A[m] < target) {
l = m + 1;
}
else {
r = m - 1;
}
}
return l;
}
int main() {
int num[] = {1};
printf("%d\n", searchInsert(num, sizeof(num)/sizeof(num[0]), 4));
return 0;
}
Input
Output
#3 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int lo = 0, hi = nums.size() - 1;
int mid = lo + (hi - lo) / 2;
while(lo < = hi){
if(nums[mid] == target) return mid;
if(nums[mid] > target) hi = mid - 1;
else lo = mid + 1;
mid = lo + (hi - lo) / 2;
}
return lo;
}
};
Input
Output
#4 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left < = right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}
}
Input
Output
#5 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _035_SearchInsertPosition
{
public int SearchInsert(int[] nums, int target)
{
int lo = 0, hi = nums.Length;
while (lo < hi)
{
var mid = lo + (hi - lo) / 2;
if (nums[mid] == target) return mid;
else if (nums[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo;
}
}
}
Input
Output
#6 Code Example with Python Programming
Code -
Python Programming
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
return bisect.bisect_left(nums, target)
Input
Output
Demonstration
Leetcode - Search Insert Position Problem Solution in Javascript Leetcode