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