Question

Formatted question description: https://leetcode.ca/all/35.html

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

@tag-array

Algorithm

Binary search.

Notes

The difference between » and »>,

  • >>> appending 0 on the left
  • >> no 0 on the left

Code

Java

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

}

All Problems

All Solutions