35. 搜索插入位置

难度 简单

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1:

输入: [1,3,5,6], 5

输出: 2

示例 2:

输入: [1,3,5,6], 2

输出: 1

示例 3:

输入: [1,3,5,6], 7

输出: 4

示例 4:

输入: [1,3,5,6], 0

输出: 0

二分搜索法

public class _35搜索插入位置 {

public static void main(String[] args) {

int[] nums1 = {1, 3, 5, 6};

int res1 = searchInsert(nums1, 5); // target = 5 ; expect output = 2;

int res2 = searchInsert(nums1, 2); // target = 2 ; expect output = 1;

int res3 = searchInsert(nums1, 7); // target = 7 ; expect output = 4;

int res4 = searchInsert(nums1, 0); // target = 7 ; expect output = 0;

System.out.println("res1 = " + res1);

System.out.println("res2 = " + res2);

System.out.println("res3 = " + res3);

System.out.println("res4 = " + res4);

}

public static int searchInsert(int[] nums, int target) {

if (nums == null || nums.length == 0) return 0;

int left = 0;

int right = nums.length - 1;

while (left < right) {

int middle = (left + right) / 2;

if (nums[middle] == target)

return middle; // 找到，就返回对应索引

else if (nums[middle] < target) // 说明答案在右侧

left = middle + 1;

else if (nums[middle] > target) // 说明答案在左侧

right = middle - 1;

}

// 来到这里，说明数组里找不到目标值, left == right

// 如果当前位置的值 比 目标值 小，则说明目标值要插到当前值右边，即当前值+1

// 否则，插入到当前位置即可

return nums[left] < target ? left + 1 : left;

}

}