给出一个转动过的有序数组，你事先不知道该数组转动了多少
(例如,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。
假设数组中不存在重复项。
[编程题]在转动过的有序数组中寻找目标值
//改造版本的二分 while内部先判断是否有序 再进行二分
public int search(int[] A, int target) {
if (A==null||A.length==0) return -1;
// write code here
int left = 0, right = A.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (A[mid] == target) return mid;
if (A[left] <= A[mid]) {//若左半部分有序
//根据有序范围 判断target在左半部分 继续进入下个while循环进行二分 target<=num[mid-1]可能越界
if (A[left] <= target && target <A[mid]) right = mid - 1;
//否则不在左边那我们继续去右半部分 让它在去while下轮循环 判断并找右半部分的某个有序序列 再找元素 循环下去
else left = mid + 1;
} else {//右半部分有序的话 同理
if (A[mid + 1] <= target && target <= A[right]) left = mid + 1;
else right = mid -1;
}
}
return -1;
}
发表于 2021-03-10 20:38:07
回复(0)
import java.util.*;
public class Solution {
/**
*
* @param A int整型一维数组
* @param target int整型
* @return int整型
*/
public int search (int[] A, int target) {
// write code here
int low = 0, high = A.length - 1;
while(low < high) {
int mid = (high - low) / 2 + low;
// A[0] <= A[mid]时, A[0] <= target <= A[mid] 向前规约
// A[0] > A[mid]时, target > A[0] > A[mid] 向前规约
// A[0] > A[mid]时， target < A[mid] < A[0] 向前规约
if ((A[0] > target) ^ (A[0] > A[mid]) ^ (target > A[mid])) {
low = mid + 1;
} else {
high = mid;
}
}
return low == high && A[low] == target ? low : -1;
}
} 只可意会
发表于 2021-03-06 02:05:47
回复(0)
public int search (int[] A, int target) {
// write code here
int left = 0;
int right = A.length-1;
if(left == right){
if(A[0]==target){
return 0;
}else{
return -1;
}
}
while(left<=right){
int mid = left+(right-left)/2;
if(A[mid]==target){
return mid;
}else if(A[left]<=A[mid]){
//递增的
if(A[left]<=target&&A[mid]>target){
right = mid-1;
}else{
left = mid+1;
}
}else{
if(A[right]>=target&&A[mid]<target){
left = mid+1;
}else{
right = mid-1;
}
}
}
return -1;
}
// write code here
int left = 0;
int right = A.length-1;
if(left == right){
if(A[0]==target){
return 0;
}else{
return -1;
}
}
while(left<=right){
int mid = left+(right-left)/2;
if(A[mid]==target){
return mid;
}else if(A[left]<=A[mid]){
//递增的
if(A[left]<=target&&A[mid]>target){
right = mid-1;
}else{
left = mid+1;
}
}else{
if(A[right]>=target&&A[mid]<target){
left = mid+1;
}else{
right = mid-1;
}
}
}
return -1;
}
发表于 2021-03-05 10:45:52
回复(0)
import java.util.*;
public class Solution {
/**
*
* @param A int整型一维数组
* @param target int整型
* @return int整型
*/
public int search (int[] A, int target) {
// write code here
if(A == null || A.length == 0){
return -1;
}
int len = A.length;
if(A[0] <= A[len-1]){
return binarySearch(A,target,0,len-1);
}
int x = minArray(A);
if(target >= A[0]){
return binarySearch(A,target,0,x);
}else{
return binarySearch(A,target,x,len-1);
}
}
// 旋转数组的最小数字,输出旋转数组的最小元素的下标，缩小查找范围，剑指offer原题
public int minArray(int[] A){
int left = 0;
int right = A.length-1;
while(left < right){
int mid = left + (right-left)/2;
if(A[mid] > A[right]){
left = mid +1;
}else if(A[mid] < A[right]){
right = mid -1;
}else{
right--;
}
}
return left;
}
// 标准二分查找方法
public int binarySearch(int[] a,int target,int left,int right){
while(left <= right){
int mid = left + (right-left)/2;
if(a[mid] < target){
left = mid +1;
}else if(a[mid] > target){
right = mid-1;
}else{
return mid;
}
}
return -1;
}
}
发表于 2021-02-09 21:33:57
回复(0)
实际上旋转后的数组就是一个分段函数，我们的目标就是找到target所在的范围。仍然采用二分法的思想，我们先考虑target在[low,mid]范围内可能的情况。
1、当mid在mid1的位置时(即A[mid]>=A[low])：则只有当tagert在A[low]和A[mid]之间时，target在low和mid之间（上面红星位置）；
2、当mid在mid2的位置（A[mid]<A[low]）：当target比A[mid]小（下面红星位置）或者比A[high]大，也就是在上曲线（上面红星位置）时，target在low和mid之间。
其他情况下，target在mid和high之间。
public int search (int[] A, int target) {
int len=A.length;int low=0,high=len-1,mid;
while(low<=high){
mid=(low+high)/2;
if(A[mid]==target) return mid;
if((A[mid]>=A[low])&&(A[low]<=target&&target<A[mid]))
high=mid-1;
else if((A[mid]<A[low])&&(target<A[mid]||target>=A[high])) high=mid-1;
else low=mid+1;
}
return -1;
}
发表于 2021-01-30 10:41:22
回复(0)
先求旋转数组的最小值，即先找到数组的分界点，然后再用二分查找
/**
*
* @param A int整型一维数组
* @param target int整型
* @return int整型
*/
public static int search (int[] A, int target) {
// write code here
int left=0,right=A.length-1;
//旋转数组最小值
while(left<right){
int mid=left+(right-left)/2;
if(A[mid]<A[right]){
right=mid;
}else if(A[mid]==A[right]){
right--;
}else{
left=mid+1;
}
}
if(left==0){
System.out.println(left);
return binarySearch(A,target,0,A.length-1);
}
int min= A[left];
int max=A[left-1];
if(target>max){
return -1;
}
if(target<min){
return -1;
}
if(target>=A[0]){
return binarySearch(A,target,0,left-1);
}else{
return binarySearch(A,target,left,A.length-1);
}
}
public static int binarySearch(int []a,int target,int left,int right){
int low=left,high=right;
while(low<=high){
int mid=low+(high-low)/2;
if(a[mid]==target){
return mid;
}else if(a[mid]<target){
low=mid+1;
}else{
high=mid-1;
}
}
return -1;
}
发表于 2021-01-09 21:58:04
回复(0)
class Solution {
public int search(int[] nums, int target) {
// 二分法查找元素
// 7 6 0 1 2 3 4 5 | 4 5 6 7 0 1 2 3
if(nums == null || nums.length == 0)
return -1;
int left = 0;
int right = nums.length - 1;
// 二分找,这里需要等于，因为等于时可能正好是target
while(left <= right){
// 这样写才不会有溢出可能
int mid = left + (right - left) / 2;
if (target == nums[mid]) {
return mid;
}
// 前半部分有序
if( nums[left] <= nums[mid]){
// 若 nums[mid] > target >= nums[left],不用比较mid == target 因为若等于则在while下第一条判断就已输出
if( target < nums[mid] && target >= nums[left] ){
// 向前规约
right = mid - 1;
}else{
// 有序部分未找到，则往后半部分无序的找
left = mid + 1;
}
}else{
// 后半部分有序
// 若nums[mid] < target <= nums[right]
if( target > nums[mid] && target <= nums[right] ){
// 向右规约
left = mid + 1;
}else{
// 有序部分未找到，则往前半部分无序的找
right = mid - 1;
}
}
}
// 未找到
return -1;
}
}
发表于 2020-12-03 22:57:57
回复(0)
1. 二分搜索变种查找旋转点，旋转点将数组分割为两个自数组
2. 分别对两个子数组按二分搜索查找目标值即可
import java.util.*;
public class Solution {
/**
*
* @param A int整型一维数组
* @param target int整型
* @return int整型
*/
public int search (int[] A, int target) {
// 1.二分找到旋转点
// 2.对旋转点左右两个部分按二分法寻找目标值
if(A == null || A.length == 0){
return -1;
}
int turnIndex = 0;
int left = 0, right = A.length - 1;
while(left <= right) {
int m = left + (right - left) / 2;
if(A[m] > A[left]) {
turnIndex = left;
left = m + 1;
} else {
right = m - 1;
}
}
int s = binarySearch(A, 0, turnIndex, target);
if(s == -1){
s = binarySearch(A, turnIndex + 1, A.length - 1, target);
}
return s;
}
private int binarySearch(int[] A, int left, int right, int target){
while(left <= right) {
int m = left + (right - left) / 2;
if(A[m] < target) {
left = m + 1;
} else if (A[m] > target) {
right = m - 1;
} else {
return m;
}
}
return -1;
}
}
发表于 2020-11-24 23:57:22
回复(0)
题解的关键在 “二分” 而不是 “旋转” ，二分就是利用当前条件来判断下一次的边界在哪里，管他有没有旋转，条件是足够的！
Step 1、 和普通有序数列二分一样，左右边界依旧是 0 和 length-1，中点是 （左+右）/ 2；
Step 2、 判断中点值是否为目标值，若是的话直接返回，若不是 开始判断下一个我们找的区域在左边还是右边。
Step 3、若A[中]>=A[左]，说明中点左边的序列是有序的，有序好办了，判断一下目标值和两个边界的大小，若目标值在这个区间内，下一次循环就在左边的区域；若不在则下次循环就在右边的区域。
Step 4、若A[中]<A[左]，说明中点右边的序列是有序的（跟上一步道理相同，这一点想通了就好说了，可以根据例子来理解），同样，有序的话就很容易判断目标值在不在这个区域内，从而得出下次循环的区域。
重复2、3、4。
上代码：
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;
}
}
发表于 2020-11-23 22:21:18
回复(2)
二分查找，分在左有序区间和右有序区间这两种情况进行讨论即可。
public class Solution {
/**
*
* @param A int整型一维数组
* @param target int整型
* @return int整型
*/
public int search (int[] A, int target) {
// write code here
if(A == null || A.length == 0){return -1;}
int len = A.length;
int bound = A[0];
int l = 0, r = len - 1;
while(l < r){
int mid = l + ((r - l) >> 1);
int midNum = A[mid];
if(midNum == target){return mid;}
if(target >= bound){
if(midNum < target && midNum >= bound){l = mid + 1;}
else{r = mid;}
}else{
if(midNum > target && midNum < bound){ r = mid;}
else{l = mid + 1;}
}
}
return A[l] == target ? l : -1;
}
}
编辑于 2020-11-23 19:49:09
回复(0)
public class Solution {
public int search(int[] A, int target) {
//二分查找
int low = 0, high = A.length - 1;
while (low <= high) {
int middle = low + (high - low) / 2;
if(A[middle] == target)
return middle;
//在左半有序部分
if (target >= A[0]) {
if(A[middle] < target && A[middle] >= A[0]){
low = middle + 1;
}else{
high = middle - 1;
}
}else{ //在右半有序部分
if(A[middle] > target && A[middle] < A[0]){
high = middle - 1;
}else{
low = middle + 1;
}
}
}
return -1;
}
}
发表于 2020-07-15 11:11:05
回复(0)
将左边界存成非正数，每次求中间点值的时候把下标取下模，其他和正常二分查找一样
public class Solution {
public int search(int[] A, int target) {
if(A == null || A.length == 0) return -1;
int max = 0;
for(int i = 0; i < A.length; i++){
if(A[max] < A[i]) max = i;
}
int right = max;
int left = max+1-A.length;
while(left <= right){
int mid = (right-left)/2+left;
if(A[(mid+A.length)%A.length] == target){
return (mid+A.length)%A.length;
}else if(A[(mid+A.length)%A.length] > target){
right = mid-1;
}else if(A[(mid+A.length)%A.length] < target){
left = mid+1;
}
}
return -1;
}
}
编辑于 2018-03-21 22:54:57
回复(0)
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;
}
}
编辑于 2017-03-26 18:10:04
回复(0)
public class Solution { public int search(int[] A, int target) { int lo = 0; int hi = A.length - 1; while (lo < hi) { int mid = (lo + hi) / 2; if (A[mid] == target) return mid; if (A[lo] <= A[mid]) { if (target >= A[lo] && target < A[mid]) { hi = mid - 1; } else { lo = mid + 1; } } else { if (target > A[mid] && target <= A[hi]) { lo = mid + 1; } else { hi = mid - 1; } } } return A[lo] == target ? lo : -1; }
发表于 2017-03-12 15:04:12
回复(0)
问题信息
难度：
17条回答
220收藏
26302浏览
通过挑战的用户
-
2022-10-27 20:58:28
-
2022-09-27 11:38:33 -
2022-09-13 18:26:51
-
2022-08-09 10:21:41
-
2022-08-01 17:44:31
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
class Solution { public: int search(int A[], int n, int target) { for(int i=0;i<n;i++) if(A[i]==target) return i; return -1; } };class Solution { public: int search(int A[], int n, int target) { int first=0; int last=n-1; while(first<=last) { int mid=first+(last-first)/2; if(A[mid]==target) return mid; if(A[first]<=A[mid])//左边有序 { if(A[first]<=target&&target<A[mid]) last=mid-1; else first=mid+1; } else//右边有序 { if(A[mid]<target&&target<=A[last]) first=mid+1; else last=mid-1; } } return -1; } };