当前位置：网站首页>Leetcode advanced path - Search insertion location

Leetcode advanced path - Search insertion location

2022-06-10 21:18:00 【Li_ XiaoJin】

 Given a sort 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 to where it will be inserted in sequence .

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

 Example  1:

 Input : [1,3,5,6], 5
 Output : 2


 Example  2:

 Input : [1,3,5,6], 2
 Output : 1


 Example  3:

 Input : [1,3,5,6], 7
 Output : 4


 Example  4:

 Input : [1,3,5,6], 0
 Output : 0

Tips in the title “ Given a sort array ”, So we can think of the binary search algorithm . Two points search （Binary Search） It is also called half search . Binary search has two requirements , One is that the sequence of numbers is orderly , The other is that the sequence uses a sequential storage structure （ For example, array ）. About several common search algorithms , You can learn it by yourself later , It's quite common .

You can look at ,http://data.biancheng.net/view/122.html

public class SearchInsertPosition {
    public int searchInsert(int[] nums, int target) {
        int temp = 0;
        if (nums.length == 1) {
            if (nums[0] >= target) {
                return temp;
            } else {
                temp++;
                return temp;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                return i;
            } else {
                if (target > nums[i]) {
                    temp++;
                } else if (target < nums[i]) {
                    return i;
                }
            }
        }

        return temp;
    }

    /**
     *  Two points search 
     * @param nums
     * @param target
     * @return
     */
    public int searchInsert1(int[] nums, int target) {
        int n = nums.length;
        int left = 0, right = n - 1, ans = n;
        while (left <= right) {
            int mid = ((right - left) >> 1) + left;
            if (target <= nums[mid]) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        SearchInsertPosition search = new SearchInsertPosition();
        int[] nums = new int[]{1,3,5,6};
//        int[] nums = new int[]{1};
        System.out.println(search.searchInsert1(nums, 7));
    }
}