LeetCode <二分搜索>34.Find First and Last Position of Element in Sorted Array
原创LeetCode <二分搜索>34.Find First and Last Position of Element in Sorted Array
原创
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]题目大意：这个是一个有序数组中查找一个数子出现的起始位置和终止位置，如果没有这个数字返回[-1,-1];
解法：
解题思路：有序数组，题目要求的复杂度为O(logn)，很容易想到采用二分查找法。但是本题采用的二分查找法与一般的二分查找法有所不同，这里我们要找到第一次和最后一次出现的target值，因此我们就不能找到了target值后就立即返回，而是应该继续搜索，直到找到最左边和最后边的target值。
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;
}上面程序中，firstOrLast为true时，寻找Fisrt,为false时候，寻找last。
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!二、旋转数组的最小元素
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1
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;
}
总结:
不管是那种方法，即使是相等的情况也要查找，因此必须while（）加上等于号
不同点：
- 不直接返回，采用变量记录 if(nums[mid]== target) resIndex = mid;
- nums[mid]>=target 含有等于号
- 注意不是大于小于等于三选一，等于必须要，大于小于是二选一
这个解法比较巧妙的是可以获取到最前和最后出现的值target值，这个与以往的二分搜索不同在于：不能找到了target值后就立即返回，而是应该继续搜索。在有序的数组中查找，我们首先应该想到的就是采用二分搜索。二分搜索也有一些变形，例如《LeetCode 33 & 81 Search in Rotated Sorted Array I&II》，需要好好消化。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。