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 <= 10⁴
-10⁴ <= nums[i] <= 10⁴
nums contains distinct values sorted in ascending order.
-10⁴ <= target <= 10⁴

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
    }
}

35 - Search Insert Position

Question

Algorithm

Notes

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Notes

Code

All Problems

All Solutions