題目：在翻轉有序中搜索

難度：Medium

題目內容：

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e.,?[0,1,2,4,5,6,7]?might become?[4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return?-1.

You may assume no duplicate exists in the array.

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

翻譯：

假設一個按升序排序的數組在事先不知道旋轉點的情況下翻轉。

(即。0,1,2,4,5,6,7可能變成4,5,6,7,0,1,2)。

您獲得了搜索的目標值。如果在數組中找不到它的索引，否則返回-1。

數組中不存在重復。

您的算法的運行時復雜度應該為O(log n)

我的思路：要復雜度O(log n)，但是數組只是基本有序，而排序算法的最佳情況也要O(N)，本弱雞想不出什么很好方法。。。

那就強行上吧，先插入排序一波，再二分法搜索。

然而最后要返回下標，再排序后下標會發生變化，所以再新建一個數組存儲下標，在排序過程中，此數組相應的值跟著一起移動。

MyCode：

1 public int search(int[] nums, inttarget) {2 int[] index = new int[nums.length];3 for (int i = 0; i < nums.length; i++) {4 index[i] =i;5 }6 insertSort(nums, index);7 returnbinaryFind(nums, target, index);8 }9

10 static int binaryFind(int[] nums, int target, int[] index) {11 int low = 0;12 int high = nums.length - 1;13 while (low <=high) {14 int mid = low + (high - low)/2;15 if (nums[mid] ==target) {16 returnindex[mid];17 } else if (nums[mid] >target) {18 high = mid - 1;19 } else{20 low = mid + 1;21 }22 }23 return -1;24 }25

26 static void insertSort(int[] nums, int[] index) {27 for (int i = 1; i < nums.length; i++) {28 int temp =nums[i];29 int temp2 =index[i];30 int j = i - 1;31 while (j > -1 && nums[j] >temp) {32 nums[j+1] =nums[j];33 index[j+1] =index[j];34 j--;35 }36 nums[j+1] =temp;37 index[j+1] =temp2;38 }39 }

我的算法復雜度：O(N2)，因為插入排序的最壞情況就是O(N2)。

編碼過程中出現的問題：

1、把插入排序的邏輯給忘了。。

答案代碼：

1 public int search(int[] A, inttarget) {2 int n =A.length;3 int lo=0,hi=n-1;4 while(loA[hi]) lo=mid+1;7 else hi=mid;8 }9 int rot=lo;10 lo=0;hi=n-1;11 while(lo<=hi){12 int mid=(lo+hi)/2;13 int realmid=(mid+rot)%n;14 if(A[realmid]==target)returnrealmid;15 if(A[realmid]

答案復雜度：O(logN)

答案思路：首先利用數組局部仍然有序的特點，和?A[mid]>A[hi]?的條件，以二分法定位到最小的那一個值的下標，注意當?A[mid]<=A[hi]?的時候，應該是hi=mid，因為此時的mid有可能就是最小點，所以不能放過。【當要求的點不是直接定位的mid的時候(等循環結束)，mid 有可能就是最終的值，下一層的 lo 和 hi 的取值不能都把mid排除， 其中一個就是mid】

找到最小點后，記錄下來，然后繼續對原數組進行二分法搜索，然而，參與比較的mid應該改成realMid=(mid+rot)%n

以[4,5,6,7,0,1,2]為例，找到最小值(真起點)0的下標4后，取mid=(0+6)/2 = 3，而真正的中點下標應該等于(mid+rot)%n = (3+4)%7 = 0

之后的向左右移動是一樣的，所以還是變化mid的值即可。

總結

以上是生活随笔為你收集整理的in the java search_LeetCode第[33]题(Java)：Search in Rotated Sorted Array的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。