Search Insert Position Leetcode Solution
In this tutorial, we will solve a leetcode problem search insert position in python.
Task:
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:
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
low, high = 0, len(nums)-1
while low <= high:
n = (low + high) // 2
if nums[n] == target:
return n
elif nums[n] > target:
high = n - 1
elif nums[n] < target:
low = n + 1
nums.append(target)
nums = sorted(nums)
return nums.index(target)
Steps:
step1: This problem is based on a Binary search algorithm.
step2: first we set two pointers left and right to the 0 and len(nums)-1.
step3: Now, we loop till the l <= r.
step4: Inside the while loop declares a variable n which will work as the middle index of the binary search array.
step5: Now, we check certain conditions on the middle index if it has the desired target then we return it and update the pointers accordingly.
step6: Now, if we make out of the loop that means our target is not present in the array, so in order to add it on the array we first append the target and then sort it.
step7: Now, we return the index of our target.
