Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/35.html
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
Algorithm
Binary search.
Notes
The difference between » and »>,
>>>
appending 0 on the left>>
no 0 on the left
Code
-
import java.util.Arrays; public class Search_Insert_Position { public static void main (String[] args) { Search_Insert_Position out = new Search_Insert_Position(); Solution s = out.new Solution(); System.out.println(s.searchInsert(new int[]{1}, 0)); System.out.println("(3 + 2)>>1: " + ((3 + 2)>>1)); System.out.println("(3 + 2)>>>1: " + ((3 + 2)>>>1)); } public class Solution { public int searchInsert(int[] nums, int target) { if(nums == null || nums.length == 0) { return 0; } int i = 0; int j = nums.length - 1; while(i <= j) { int mid = i + (j - i) / 2; if(nums[mid] == target) { // if found return mid; // } else if(mid - 1 >= 0 && mid + 1 < nums.length && nums[mid - 1] < target && target < nums[mid]) { // if not found // return mid; // } else if(i == 0 && target < nums[i]) { // corner case // return i; } else if(nums[mid] < target) { i = mid + 1; } else { j = mid - 1; } } return i; // @note: accepted // return i + 1; // @note: wrong // return j + 1; // @note: accepted } } // lazy public class Solution222 { public int searchInsert(int[] A, int target) { if (A == null || A.length == 0) return 0; /* * @note: Returns: * index of the search key, if it is contained in the array; otherwise, (-(insertion point) - 1) */ int ind = Arrays.binarySearch(A, target); if (ind >= 0) return ind; else return (ind + 1) * (-1); } } } ############ class Solution { public int searchInsert(int[] nums, int target) { int left = 0, right = nums.length; while (left < right) { int mid = (left + right) >>> 1; if (nums[mid] >= target) { right = mid; } else { left = mid + 1; } } return left; } }
-
// OJ: https://leetcode.com/problems/search-insert-position/ // Time: O(logN) // Space: O(1) class Solution { public: int searchInsert(vector<int>& A, int target) { int L = 0, R = A.size() - 1; while (L <= R) { int M = (L + R) / 2; if (A[M] == target) return M; if (A[M] < target) L = M + 1; else R = M - 1; } return L; } };
-
class Solution: def searchInsert(self, nums: List[int], target: int) -> int: left, right = 0, len(nums) while left < right: mid = (left + right) >> 1 if nums[mid] >= target: right = mid else: left = mid + 1 return left ############ ''' bisect.bisect_left(a, x, lo=0, hi=len(a), *, key=None) Locate the insertion point for x in a to maintain sorted order. The parameters lo and hi may be used to specify a subset of the list which should be considered; by default the entire list is used. If x is already present in a, the insertion point will be before (to the left of) any existing entries. The return value is suitable for use as the first parameter to list.insert() assuming that a is already sorted. https://docs.python.org/3/library/bisect.html ''' class Solution: def searchRange(self, nums: List[int], target: int) -> List[int]: l = bisect_left(nums, target) r = bisect_left(nums, target + 1) return [-1, -1] if l == r else [l, r - 1] class Solution(object): def searchInsert(self, nums, target): """ :type nums: List[int] :type target: int :rtype: int """ lo = 0 hi = len(nums) while lo < hi: mid = lo + (hi - lo) / 2 if nums[mid] > target: hi = mid elif nums[mid] < target: lo = mid + 1 else: return mid return lo
-
func searchInsert(nums []int, target int) int { left, right := 0, len(nums) for left < right { mid := (left + right) >> 1 if nums[mid] >= target { right = mid } else { left = mid + 1 } } return left }
-
/** * @param {number[]} nums * @param {number} target * @return {number} */ var searchInsert = function (nums, target) { let left = 0; let right = nums.length; while (left < right) { const mid = (left + right) >> 1; if (nums[mid] >= target) { right = mid; } else { left = mid + 1; } } return left; };
-
use std::cmp::Ordering; impl Solution { pub fn search_insert(nums: Vec<i32>, target: i32) -> i32 { let mut left = 0; let mut right = nums.len(); while left < right { let mid = left + (right - left) / 2; match nums[mid].cmp(&target) { Ordering::Less => left = mid + 1, Ordering::Greater => right = mid, Ordering::Equal => return mid as i32, } } left as i32 } }