34. Find First and Last Position of Element in Sorted Array
Description
描述：https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/description/ 题意：在有序数组中，查找目标数的第一次和最后一次出现的下标，没有则返回-1。
Solution: (Java)
class Solution {
public int[] searchRange(int[] nums
, int target
) {
int[] indexs
= new int[2];
int left
= 0, right
= nums
.length
-1, mid
, first
= -1, last
= -1;
indexs
[0] = -1;
indexs
[1] = -1;
while (left
<= right
) {
mid
= (left
+ right
) / 2;
if (nums
[mid
] == target
) {
first
= mid
;
last
= mid
;
while (first
>= 0) {
if (nums
[first
] == target
) {
indexs
[0] = first
;
first
--;
} else
break;
}
while (last
<= nums
.length
-1) {
if (nums
[last
] == target
) {
indexs
[1] = last
;
last
++;
} else
break;
}
break;
} else if (nums
[mid
] > target
) {
right
= mid
- 1;
} else {
left
= mid
+ 1;
}
}
return indexs
;
}
}
思路
二分法查找，复杂度要求O(log n)；稍微变动二分查找即可，在找到目标之后，往目标的左右两边扩展查找即可；改进：在找到目标后往两边扩展时，还可以继续用二分法。
