给出一个转动过的有序数组,你事先不知道该数组转动了多少
(例如,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; }
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; } }只可意会
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; } }
/** * * @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; }
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; } }
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; } }
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; } }
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; } }
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; } }
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; } }
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; } }
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; }