# 34.Find First and Last Position of Element in Sorted Array

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

Example 1:

```Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]```

Example 2:

```Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]```

## 解法：

```    public int[] searchRange(int[] nums, int target) {
return new int[]{findFirstOrLast(nums,target,true),findFirstOrLast(nums,target,false)};
}

public int findFirstOrLast(int[] nums, int target,boolean firstOrLast){
int resIndex = -1;
int left = 0;
int right = nums.length-1;
int mid;
while (left<=right){
mid = left + (right - left)/2;
if (firstOrLast)
if (nums[mid]>=target) right = mid -1;
else left = mid+1;
else
if (nums[mid]<=target) left = mid+1;
else right = mid-1;
if (nums[mid] == target) resIndex = mid;
}
return resIndex;
}```

```public static int Binary(int[] arr, int key, int low, int high) {
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] > key) {
high = mid - 1;
} else if (arr[mid] < key) {
low = mid + 1;
} else {
return mid;
}
}
return -1;
}

while (left<=right){
mid = left + (right - left)/2;
if (nums[mid]>=target) right = mid -1;
else left = mid+1；
if (nums[mid] == target) resIndex = mid;
}

```
``` if (nums[mid] == target) resIndex = mid; Look at this step after the if_else conditions are done. In
FIndFirst, he makes idx move towards the lower index, and in FIndLast he makes it move towards the
higher index. The loop doesn't exist even if the target is found, it moves to one end, (left==right)
and then exits. It's really smart!```

# 二、旋转数组的最小元素

```    public int minNumberInRotateArray(int [] array) {
if(array.length == 0) return 0;

int left = 0;
int right = array.length-1;
while(left<=right){
int mid = left + (right - left)/2;

if(mid-1>0 && array[mid]<array[mid-1]){
return array[mid];
}
// 说明左半部分是递增的
if (array[left]<array[mid]){
left = mid + 1;
}
// 说明右半部分是递增的
if (array[right]>array[mid]){
right = mid - 1;
}
}
return 0;
}```

## 总结:

1. 不直接返回，采用变量记录 if(nums[mid]== target) resIndex = mid;
2. nums[mid]>=target 含有等于号
3. 注意不是大于小于等于三选一，等于必须要，大于小于是二选一

143 篇文章23 人订阅

0 条评论

## 相关文章

1925

3065

813

1461

1013

913

### HashSet/HashMap详解

HashMap和HashSet是Java Collection接口两个重要的成员，其中HashMap是Map接口常用的实现类，HashSet是Set接口常用...

23410

3939

3085

1202