Search for insertion 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, return the position where it will be inserted in order.

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

Examples can be found on the LeetCode website.

Source: LeetCode link: leetcode-cn.com/problems/se… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Solution 1: brute force cracking method
  • First, if nums is null or null, return 0;
  • Iterating from the first element of nums, returns the index bit of the current element if target is not greater than the current element;
  • If no element larger than target is found, nums.length is returned.
Solution two: binary search method

Binary search solution, 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 {
    /** * Brute force method **@param nums
     * @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) {
                returni; }}return nums.length;
    }

    /** * binary search method **@param nums
     * @param target
     * @return* /
    public static int searchInsert2(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)); }}Copy the code

As long as you run, the world runs with you. Set a direction, run hard, the world will make way for you.