[LeetCode]35. Search Insert Position(Easy)
Mar 12, 2021
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.
Example 1:
Input: nums = [1,3,5,6], target = 5
Output: 2Example 2:
Input: nums = [1,3,5,6], target = 2
Output: 1Solution 1:
Linear Search. Time complexity O(N), N= Length of nums.
Solution 2:
Binary Search. Time complexity O(log(N)), N= Length of nums. When the nums did not contain the target number. In the end of the while loop, leftIndex would equal rightIndex. And if nums[midIndex] > target, the index of target should be midIndex. Otherwise, the the index of target should be midIndex+1.