给出一个转动过的有序数组,你事先不知道该数组转动了多少
(例如,0 1 2 4 5 6 7可能变为4 5 6 7 0 1 2).
在数组中搜索给出的目标值,如果能在数组中找到,返回它的索引,否则返回-1。
假设数组中不存在重复项。
(例如,0 1 2 4 5 6 7可能变为4 5 6 7 0 1 2).
在数组中搜索给出的目标值,如果能在数组中找到,返回它的索引,否则返回-1。
假设数组中不存在重复项。
class Solution { public: // 不要被“旋转”而迷惑,“有序”并不是二分查找的核心 // 二分查找的核心是"通过界桩快速决定查找方向,大幅缩短查找空间" // 只要能快速确定界桩,就能使用二分查找 // 充分利用有序数组能够快速获取边界值的特性 // 利用这一特性可以快速确定目标值应处的区间 int search(vector<int>& nums, int target) { if (nums.empty()) return -1; int lo = 0, hi = nums.size() - 1; while (lo <= hi) { int mi = lo + ((hi - lo) >> 1); if (nums[mi] == target) return mi; // 只要在普通的二分查找判断语句中加一层 && 来确定目标值所在的区间,即可以同样O(logn)的复杂度查找 if (nums[lo] <= nums[mi] && (nums[lo] <= target && target < nums[mi])) hi = mi - 1; else if (nums[mi] <= nums[hi] && !(nums[mi] < target && target <= nums[hi])) hi = mi - 1; else lo = mi + 1; } return -1; } };
public class Solution {
public int search(int[] A, int target) {
if(A == null || A.length == 0){
return -1;
}
int begin = 0;
int end = A.length - 1;
if(A[begin] < A[end]){
return binarysearch(A, begin, end, target);
}else{
while(A[begin] > A[end]){
if(end - begin == 1){
break;
}
int mid = (begin + end)/2;
if(A[mid] > A[begin]){
begin = mid;
}else{
end = mid;
}
}
if(target >= A[0]){
return binarysearch(A, 0, begin, target);
}else{
return binarysearch(A, begin+1, A.length - 1, target);
}
}
}
public int binarysearch(int[] A, int begin, int end, int target){
if(A == null || A.length == 0){
return -1;
}
while(begin <= end){
int mid = (begin + end)/2;
if(A[mid] > target){
end = mid - 1;
}else if(A[mid] < target){
begin = mid + 1;
}else{
return mid;
}
}
return -1;
}
}
class Solution { public: /** * L M R * |-------|---|-------| * | 0 1 2 | 4 | 5 6 7 | * | 7 0 1 | 2 | 4 5 6 | * T | 6 7 0 | 1 | 2 4 5 | * | 5 6 7 | 0 | 1 2 4 | * |-------|---|-------| * | 4 5 6 | 7 | 0 1 2 | * B | 2 4 5 | 6 | 7 0 1 | * | 1 2 4 | 5 | 6 7 0 | * |-------|---|-------| */ int search(int A[], int n, int target) { int lo = 0, hi = n - 1; while(lo <= hi) { int mid = (lo + hi) >> 1; if(A[mid] == target) return mid; if(A[mid] < A[hi] && A[mid] < target && target <= A[hi]) lo = mid + 1; // target在T区 且 在L+M区 else if(A[mid] > A[hi] && !(A[lo] <= target && target < A[mid])) lo = mid + 1; // target在B区 且 不在L+M区 else hi = mid - 1; } return -1; } };
对旋转数组进行均等划分后,总有一边是有序的,如:
10 11 12 13 14 15 1 2 3
10 11 15 1 2 3 4 5 6 7 8
我们定位到有序的一边后,对比target
与有序子数组的左右边界,就可以作出搜索左侧还是右侧的决策。
代码如下:
第16行必须是
<=
,不能是<
,举例——从[3,1]
中查找1
// // Created by jt on 2020/9/3. // class Solution { public: /** * * @param A int整型一维数组 * @param n int A数组长度 * @param target int整型 * @return int整型 */ int search(int* A, int n, int target) { // write code here int left = 0, right = n - 1; while (left <= right) { int mid = left + (right - left) / 2; if (A[mid] == target) return mid; if (A[mid] >= A[left]) { // 左侧有序(含A[mid]) if (A[mid] > target && A[left] <= target) right = mid - 1; else left = mid + 1; } else { // 右侧有序(含A[mid]) if (A[mid] < target && A[right] >= target) left = mid + 1; else right = mid - 1; } } return -1; } };
class Solution { public: // 二分查找 int search(int A[], int n, int target) { int left = 0,middle,right = n-1; while(left <= right) { middle = (right+left)>>1; if(A[middle] == target) return middle; if(A[left] <= A[middle]) /// left side is sorted { if(A[left] <= target && target < A[middle]) right = middle-1; else left = middle+1; } else /// right side is sorted { if(A[middle] < target && target <= A[right]) left = middle+1; else right = middle-1; } } return -1; } };
class Solution { public: /** * * @param A int整型一维数组 * @param n int A数组长度 * @param target int整型 * @return int整型 */ int search(int* A, int n, int target) { // write code here if(A[0]>A[n-1]) { int mid=n/2; if(A[0]<A[mid]) { while(A[0]<A[mid]&&mid<(n-1)) { mid++; } } else { while(A[0]>A[mid]) { mid--; } } if(target>=A[0]) return binarySearch(A, 0, mid, target); else return binarySearch(A, mid+1, n-1, target); } else { return binarySearch(A, 0, n-1, target); } } int binarySearch(int *A,int start,int end,int target) { if(target==A[start]) return start; if(target==A[end]) return end; if(start==end||(start+1)==end) return -1; if(A[(start+end)/2]==target) return (start+end)/2; if(A[(end+start)/2]<target) { return binarySearch(A, (end+start)/2, end, target); } else { return binarySearch(A, start, (end+start)/2, target); } } };
class Solution { public: /** * * @param A int整型一维数组 * @param n int A数组长度 * @param target int整型 * @return int整型 */ int search(int* A, int n, int target) { // write code here int left=0;int right=n-1; while(left<right) { int mid=left+(right-left)/2; if(A[mid]==target) return mid; if(A[mid]<=A[right]) { if(target>A[mid]&&target<=A[right]) left=mid+1; else right=mid-1; } else { if(target<A[mid]&&target>=A[left]) right=mid-1; else left=mid+1; } } if(A[left]==target) return left; else return -1; } };
import java.util.*; public class Solution { public int search (int[] A, int target) { int left_point = 0; int right_point = A.length-1; int mid; while(left_point<=right_point){ mid = (left_point + right_point)/2; if (A[mid] == target) return mid; if (A[mid]>=A[left_point]){//左边区域有序 if(target>A[left_point]&&target<A[mid]){ right_point = mid; //左边找 }else{ left_point = mid+1;//右边找 } } else{//右边区域有序 if(target<A[right_point]&&target>A[mid]){ left_point = mid+1;//右边找 } else{ right_point = mid;//左边找 } } } return -1; } }
import java.util.*; public class Solution { private static int bs(int[] arr, int target, int begin, int end) { if (begin == end) { if (target == arr[begin]){ return begin; } else{ return -1; } } int middle = begin + (end - begin)/2; if (target == arr[middle]) { return middle; } /* if array only has 2 numbers */ if (middle == begin) { if (target == arr[end]) { return end; } else { return -1; } } if (arr[begin] <= arr[middle-1]){ if (arr[begin] <= target && target <= arr[middle-1]) { return bs(arr,target, begin,middle-1); } else { return bs(arr,target, middle+1,end); } } else { if (arr[middle+1] <= target && target <= arr[end]) { return bs(arr,target, middle+1,end); } else { return bs(arr,target, begin,middle-1); } } } /** * * @param A int整型一维数组 * @param target int整型 * @return int整型 */ public int search (int[] A, int target) { return bs(A, target, 0, A.length-1); } }
判断target在中间的左边还是右边。判断某边时,需判断是在左边有序还是右边有序(若存在)中。class Solution { public: /** * * @param A int整型一维数组 * @param n int A数组长度 * @param target int整型 * @return int整型 */ int search(int* A, int n, int target) { // write code here int left = 0, right = n; while(left < right) { int m = (left) + ((right-left)>>1); if(A[m] == target) return m; if(A[left] <= A[m] && !(A[left] <= target && target < A[m])){ left = m+1; } else if(A[left] > A[m] && (A[m] < target && target <= A[right-1])) { left = m+1; } else right = m; } return -1; } };
方法一 class Solution { public: int search(int A[], int n, int target) { map<int,int>m; if(target==A[0]) return 0; for(int i=0;i<n;i++) m[A[i]]=i; return m[target]>0?m[target]:-1; } }; 方法二 class Solution { public: int search(int A[], int n, int target) { for(int i=0;i<n;i++) if(target==A[i]) return i; return -1; } };
class Solution { public: int search(int A[], int n, int target) { int l = 0,h = n-1; while(l <= h) { int mid = (l+h)/2; if(A[mid] == target) return mid; if(A[l] <= A[mid]) { if(A[l] <= target && target <= A[mid]) h = mid - 1; else l = mid + 1; }else{ if(A[mid] <= target && target <= A[h]) l = mid + 1; else h = mid - 1; } } return -1; } };
public class Solution { public int search(int[] A, int target) { int position = 0; for (int i = 1; i < A.length; i ++) { if(A[i] < A[i - 1]) position = i - 1; } int search1 = binarySearch(A, 0, position, target); int search2 = binarySearch(A, position + 1, A.length - 1, target); if(search1 == - 1 && search2 == - 1) return - 1; return search1 == - 1 ? search2 : search1; } public int binarySearch(int[] arr, int low, int high, int target) { while (low <= high) { int mid = (low + high) / 2; if(arr[mid] < target) low = mid + 1; else if(arr[mid] > target) high = mid - 1; else return mid; } return - 1; } }
//题意:经过一次旋转的有序数组中,找到target数,并返回其位置 //使用二分查找,先找出有序数组分界点,如果target大于第一个数,则在左半边二分查找,反之在右边二分查找。 //分界点即数组最小点,亦可二分查找left,right逐步确定分界点(若是重复数组,只能乖乖顺序查找分界点) public class Solution { public int search(int[] A, int target) { int left=0; int right=A.length-1; if(left==right){ if(A[0]==target) return 0; else return -1; } int mid; while(left<right-1){//为了寻找分界点 mid=(right-left)/2+left;// 直接使用(high + low) / 2 可能导致溢出 if(A[mid]>A[left]){ left=mid; } if(A[mid]<A[right]){ right=mid; } } int min=right;//得出分界点 if(A[0]<=target){//在(第一点到分界点)左半部分二分查找 left=0; right=min-1; while(left<=right){ mid=(right-left)/2+left; if(A[mid]==target){ return mid; } else if(A[mid]>target){ right=mid-1; } else{ left=mid+1; } } } if(A[A.length-1]>=target){//在(分界点到最后一点)右半部分二分查找 left=min; right=A.length-1; while(left<=right){ mid=(right-left)/2+left; if(A[mid]==target){ return mid; } else if(A[mid]>target){ right=mid-1; } else{ left=mid+1; } } } return -1; } }
public class Solution { public int search(int[] a, int target) { int len=a.length; if(len==0){ return -1; } int low=0; int high=len-1; int mid=0; while(low<=high){ mid=(low+high)/2; if(a[mid]==target){ return mid; } //判断是正常的排序顺序 if(a[low]<=a[high]){ if(a[mid]>target){ high=mid-1; }else{ low=mid+1; } } //否则就是存在旋转的排序 else{ //判断左边有序(low直到mid 有序,a[low]是左边最小值,a[mid]是左边序列的最大值) if(a[low]<=a[mid]){ //如果target介于a[low]与a[mid]之间,就在左边找 if(target>=a[low]&&target<a[mid]){ high=mid-1; }else{ low=mid+1; } } //判断右边有序,(mid直到high有序) else{ //如果target介于a[mid]与a[high]之间,就在右边找 if(target>a[mid]&&target<=a[high]){ low=mid+1; }else{ high=mid-1; } } } } return -1; } }