Aunt Guan is participating in the “Java Theme month – Java brush question clocking”, see the activity link for more details

First of all, I would like to clarify that every algorithm problem has multiple solutions. We will only talk about several excellent solutions in LeetCode, hoping to help you. Let’s first look at the description of the problem

I. Title Description:

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.

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

Ii. Analysis of Ideas:

When you see this problem, your first reaction should be binary search. Why? Because they say sorted array, binary search is common to find a value in an ordered array, in order log n time. How to answer it? Nums [pos-1] < target <= nums[pos] Finds the index of the first element in an ordered array that is greater than or equal to target. At this point, you should be able to take a tumble: find a value in an ordered array, using binary search. Isn’t it. Let’s cut the crap and look at the code

Code implementation

public int searchInsert(int[] nums, int target) {
    int n = nums.length;
    // Start from 0 on the left and n-1 on the right
    int left = 0, right = n - 1, ans = n;
    while (left <= right) {
        // Get the intermediate value
        // >> 1 is a bit operation, which is equivalent to dividing by two
        // Why is it right-left divided by two, and then left? Right plus left divided by two?
        int mid = ((right - left) >> 1) + left;
        if (target <= nums[mid]) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1; }}return ans;
}
Copy the code

Complexity analysis

Time complexity: O(logn) where n is the length of the array. The time required for binary search is O(logn). Space complexity: O(1). We just need constant space for a few variables

Brush question summary

If you have other ideas to solve the problem, as long as you can achieve the requirements, it is no problem, all roads lead to Rome, not just limited to the solution I said ha ~, excellent ideas and code is more learning significance, let’s work together