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.
Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0
一刷：
- 給你的數(shù)組是一個順序值亿傅，先判斷目標值是否大于最后一個數(shù)值捧搞，如果是則插入值就是最后一個數(shù)字的索引。
2.循環(huán)數(shù)組的每個元素锅必，如果目標值大于或等于這個元素的時候就替換這個元素的位置盼樟，其索引就是這個值氢卡。
public static int searchInsert(int[] nums, int target) {
int index = 0;
if (target >= nums[nums.length - 1]) {
return nums.length;
}
for (int i = 0; i < nums.length; i++) {
if (target <= nums[i]) {
index = i;
break;
}
}
return index;
}
二刷：一刷循環(huán)的話可能會遍歷整個數(shù)組，所以想到了二分法晨缴。
- 定義兩個變量
low译秦，high，分別是數(shù)組的第一個元素和最后一個元素的索引
2.循環(huán)取中間索引mid的值击碗，如果目標值和中間索引值相等筑悴，即返回中間值的索引
3.如果大于索引值，low=mid+1稍途，進入下次循環(huán)
4.如果小于索引值阁吝，high=mid-1,進入下次循環(huán)
public static int searchInsert1(int[] nums, int target) {
int low = 0, high = nums.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return low;
}
