LeetCode035-Search Insert Position

Search Insert Position

Question:

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.

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

解法代码

public class LeetCode35 {

    public int searchInsert(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int left = 0;
        int right = nums.length - 1;

        int mid = -1;
        while (left <= right) {
            // 防止溢出
            mid = left + (right - left) / 2;
            // 二分查找
            if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                // 此种情况，如果需要插入target，插入位置应该是mid的下一个位置，所以使用++mid
                left = ++mid;
            } else {
                // 匹配到值，跳出循环，返回mid
                break;
            }
        }

        return mid;
    }
}

测试代码

import static org.junit.Assert.assertEquals;

import java.util.Arrays;
import java.util.Collection;

import org.junit.Before;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.Parameterized;
import org.junit.runners.Parameterized.Parameters;

import com.kay.pro.alog.LeetCode35;

@RunWith(Parameterized.class)
public class LeetCode35Test {
    private LeetCode35 leetCode;
    private int[] nums;
    private int target;
    private int ret;
    
    public LeetCode35Test(int[] nums, int target, int ret) {
        this.nums = nums;
        this.target = target;
        this.ret = ret;
    }
    
    @Before
    public void before() {
        leetCode = new LeetCode35();
    }
    
    @Parameters
    public static Collection<?> reverserArrays() {
        return Arrays.asList(new Object[][]{
            {new int[]{1,3,5,6}, 5, 2},
            {new int[]{1,3,5,6}, 2, 1},
            {new int[]{1,3,5,6}, 7, 4},
            {new int[]{1}, 1, 0}
        });
    }
    
    @Test
    public void leetCode33() {
        assertEquals(ret, leetCode.searchInsert(nums, target));
    }
}

Output：

Time And Space Complexity

Time: 二分查找时间复杂度
Space: 不需要使用额外的存储空间，原地替换

Tips

简单的二分查找，注意nums[mid] < target找到插入位置的时候，应该是在mid的下一个位置插入，所以此处用的是left = ++mid;而不是left = mid + 1;。