題目鏈接

搜索旋轉數組

題目描述

注意點

• 數組已被旋轉過很多次
• 數組元素原先是按升序排列的
• 若有多個相同元素，返回索引值最小的一個

解答思路

• 首先需要知道的是，本題數組中的旋轉多次只是將頭部的某些元素移動到尾部，所以不論怎么旋轉，數組都是有一定順序的，最差的情況是分為兩段遞增的子數組
• 因為數組是有一定順序的，所以首先考慮二分查找搜索數組，本題數組可能是兩段遞增的子數組組成并且數組中的元素可能重復，所以要考慮多方面：
  • 如果二分后的左區間是嚴格遞增的：如果target在arr[left]~arr[mid]之間，說明target就在左區間內（不在左區間說明不存在），繼續向左二分；否則說明target在右區間內，向右二分
  • 如果二分后的左區間是由兩段遞增的子數組組成的：如果target >= arr[left]或target <= arr[mid]，說明target就在左區間內，繼續向左二分；否則說明target在右區間內，向右二分
  • 如果二分后的左區間內的值都是相同的（arr[left] = arr[mid]）：如果此時target等于該值，則直接將右邊界移動到左邊界即可（此時left就是結果值）；否則需要不斷移動左邊界（每次移動一格，清除重復值）找到target

代碼

class Solution {public int search(int[] arr, int target) {int left = 0, right = arr.length - 1;while (left < right) {int mid = left + ((right - left) >> 1);// 左區間升序if (arr[left] < arr[mid]) {// 值在左區間內if (target >= arr[left] && target <= arr[mid]) {right = mid;} else {left = mid + 1;}continue;}// 左區間不升序if (arr[left] > arr[mid]) {// 值在左區間內if (target >= arr[left] || target <= arr[mid]) {right = mid;} else {left = mid + 1;}continue;}// 左區間值都相同 if (arr[left] == arr[mid]) {// 注意清理重復值if (arr[left] != target) {left++;} else {right = left;}}}return arr[left] == target ? left : -1;}
}

關鍵點

• 二分查找的思想
• 注意邊界問題
• 注意有多個重復的target時怎么找到最小的索引