[LeetCode] 35. Search Insert Position
Given a sorted array 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 may assume no duplicates in the array.
Here are few examples.
[1,3,5,6]
, 5 → 2[1,3,5,6]
, 2 → 1[1,3,5,6]
, 7 → 4[1,3,5,6]
, 0 → 0
Thought process:
Java's Arrays class has a binarySearch method, which returns the index of the target if target is found. If the target is not found, the method will return (- (insertion point) - 1).
Solution 1:
1 2 3 4 5 6 7 8 9 10 11 | public class Solution { public int searchInsert(int[] nums, int target) { int index = Arrays.binarySearch(nums, target); if (index >= 0) { return index; } else { return - (index + 1); } } } |
Time complexity: O(logn)
Of course this solution is trivial. The interviewer is definitely going to ask "how do you do it without using the binarySearch method". The idea here is to be clear about what we are searching. In this case, we're searching for the last number that's less than or equal to target.
Solution 2:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | public class Solution { public int searchInsert(int[] nums, int target) { if (nums.length == 0) { return 0; } int start = 0; int end = nums.length - 1; while (start + 1 < end) { int mid = start + (end - start) / 2; if (nums[mid] <= target) { start = mid; } else { end = mid; } } if (nums[end] < target) { return end + 1; } else if (nums[start] >= target) { return start; } else { return start + 1; } } } |
Because the while loop will break when start is one less than end, we need to handle edge cases well. If the array is large enough, we are sure that start is the last position that's less than or equal to target. But if the array has only one or two elements, we also need to check nums[start] and nums[end].
Time complexity: O(logn).
Comments
Post a Comment