LeetCode --- 字符串、数组
简书专栏：//www.greatytc.com/nb/41796568
知乎专栏：https://zhuanlan.zhihu.com/c_174823416
一、题目描述
来源：力扣（LeetCode）
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
可以假设数组中无重复元素。
示例 :
输入: [1,3,5,6], 5
输出: 2:
输入: [1,3,5,6], 2
输出: 1
输入: [1,3,5,6], 7
输出: 4
输入: [1,3,5,6], 0
输出: 0
要求实现函数
public int searchInsert(int[] nums, int target){}
二、实现思路以及代码
2.1 思路一：暴力破解法
直接对数组进行遍历，如果等于目标值则直接返回，如果小于目标值则加一，如果大于目标值的话则返回。要是遍历完成之后还没有找到大与目标的值，则表明该数字应该插入在最后的位置。
2.1.1 暴力破解实现代码
public int searchInsert(int[] nums, int target) {
int i = 0;
while(i < nums.length) {
if(nums[i] == target) {
return i;
}
if(nums[i] < target) {
i++;
} else {
return i;
}
}
return i;
}
2.2 思路二：二分法
该问题等价于寻找target元素的左边界问题。直接用二分法即可。
二分法统一用left <= right形式
2.2.1 实现代码
public int searchInsert(int[] nums, int target) {
//题意即返回左边界
int left = 0, right = nums.length - 1;
while(left <= right) {
int mid = (left + right) >>> 1;
if(nums[mid] == target) {
right = mid - 1;
} else if(nums[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}
三、测试代码
public static void main(String[] args) {
int[] nums = {1,3,5,6};
int target = 0;
System.out.println(searchInsert(nums,target));
target = 2;
System.out.println(searchInsert(nums,target));
}
输出结果为：
0
1
