题目要求
1
2
3
4
5
6
| 在一个有序的数组中，找到一个目标值，返回该值得下标。若没有找到该值，则返回该值顺序插入的下标
例如，
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0
|
1
2
3
4
5
6
7
8
9
| public int searchInsert(int[] nums, int target) {
int index=0;
for( ; index<nums.length ; index++){
if(nums[index]>=target){
break;
}
}
return index;
}
|
使用双指针后效率比单指针效率高
1
2
3
4
5
6
7
8
9
10
11
12
13
| public int searchInsert2(int[] nums, int target) {
int pointerLeft = 0;
int pointerRight = nums.length-1;
for( ; pointerLeft<=pointerRight ; pointerLeft++, pointerRight--){
if(nums[pointerLeft]>=target){
return pointerLeft;
}
if(nums[pointerRight]<target){
return pointerRight+1;
}
}
return pointerLeft;
}
|
使用二分法也可以，但是二分法可能会在数组有重复数字情况下产生多个答案
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public int searchInsert3(int[] nums, int target) {
int pointerLeft = 0;
int pointerRight = nums.length-1;
while(pointerLeft<=pointerRight){
int mid = (pointerLeft+pointerRight)/2;
if(nums[mid]==target){
return mid;
}else if(nums[mid]>target){
pointerRight = mid-1;
}else{
pointerLeft = mid+1;
}
}
return pointerLeft;
}
|