Search for insert position

Given a sorted array and a target value, find the target value in the array and return its index. If the target value does not exist in the array, returns the position at which it will be inserted in order.

You can assume that there are no duplicate elements in the array.

See the LeetCode website for an example.

Source: LeetCode Link: https://leetcode-cn.com/probl… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

Solution one: violence crack law
  • First, if nums is null or empty, return 0;
  • If target is not greater than the current element, return the index bit of the current element.
  • If no element larger than target is found, nums.length is returned.
Solution two: binary search method

The solution of binary search, low and high are the first and last bit of the array respectively, mid is
(low+high)/2, determine whether the value of mid is equal to target, move low and high respectively according to the size, until low is not less than high, return the result. 

Public class leetCode_035 {/** ** * @Param nums * @Param target * @Return */ public class leetCode_035 {/** ** @Param target * @Return */ public class leetCode_035 {/** * @Param target * @Return */ public static int searchInsert(int[] nums, int target) { if (nums == null || nums.length == 0) { return 0; } for (int i = 0; i < nums.length; i++) { if (nums[i] >= target) { return i; } } return nums.length; Public static int searchInsert2(int[] nums, int[] nums) public static int searchInsert2(int[] nums, int[] nums, int[] nums) int target) { if (nums == null || nums.length == 0) { return 0; } int low = 0, high = nums.length - 1, mid, result = nums.length; while (low <= high) { mid = (low + high) / 2; if (nums[mid] >= target) { result = mid; high = mid - 1; } else { low = mid + 1; } } return result; } public static void main(String[] args) { int[] nums = new int[]{1, 3, 5, 6}; System.out.println(searchInsert(nums, 7)); System.out.println(searchInsert2(nums, 7)); }}

【 Daily Message 】
If you run, the world will run with you. Set a direction, run hard, the world will make way for you.