題目鏈接

/**

? ? ? ? 升序數組在某個位置被分割為前后兩部分,前后兩部分整體互換;在被改變后的數組中找到目標值

? ? ? ? O(log n)---> 二分查找

? ? ? ? 特點:

? ? ? ? ? ? 旋轉后的數組被分割為兩個獨立的遞增區間

? ? ? ? ? ? 左半區的最小值,大于右半區的最大值(mid所在區間的判斷依據)

? ? ? ? 二分策略:

? ? ? ? ? ? 首先判斷mid落在左區間還是右區間,其次判斷target是否在端點到mid之間

? ? ? ? ? ? 若target是在端點到mid之間,則可以確定target所在的半區,此時進行常規二分即可

? ? ? ? ? ? 若target不在端點到mid之間,則無法具體確定其是在mid所在半區的剩余部分,還是另一個半區

? ? ? ? ? ? 此時迭代left或right,淘汰無效部分,重新計算mid重復上述流程,直到搜尋結束或搜尋到target為止

? ? ? ? 判斷條件細化:

? ? ? ? ? ? mid所在區間:

? ? ? ? ? ? ? ? ? ? nums[left] <= nums[mid]---> mid必定在左半區,反之在右半區; 依據:左半區的最小值,大于右半區的最大值

? ? ? ? ? ? target所在區間:

? ? ? ? ? ? ? ? ? ? 若mid在左半區:nums[left] < target && target < nums[mid]--->target與mid同在左半區,繼續常規二分即可

? ? ? ? ? ? ? ? ? ? 若mid在右半區:nums[mid] < target && target < nums[right]--->target與mid同在右半區,繼續常規二分即可

? ? ? ? ? ? ? ? ? ? 若表達式不成立,則無法確定target所在半區,則淘汰無效部分重新判斷

? ? ? ? ? ? 注意事項:

? ? ? ? ? ? ? ? ? ? 由于未真正找到數組兩半區如何劃分,當target所在分區確定后,原本判斷target所處獨立分區的代碼功能會退化為常規二分,稍顯冗余無法避免

*/

class Solution {/**升序數組在某個位置被分割為前后兩部分,前后兩部分整體互換;在被改變后的數組中找到目標值O(log n)---> 二分查找特點:旋轉后的數組被分割為兩個獨立的遞增區間左半區的最小值,大于右半區的最大值(mid所在區間的判斷依據)二分策略:首先判斷mid落在左區間還是右區間,其次判斷target是否在端點到mid之間若target是在端點到mid之間,則可以確定target所在的半區,此時進行常規二分即可若target不在端點到mid之間,則無法具體確定其是在mid所在半區的剩余部分,還是另一個半區此時迭代left或right,淘汰無效部分,重新計算mid重復上述流程,直到搜尋結束或搜尋到target為止判斷條件細化:mid所在區間:nums[left] <= nums[mid]---> mid必定在左半區,反之在右半區; 依據:左半區的最小值,大于右半區的最大值target所在區間:若mid在左半區:nums[left] < target && target < nums[mid]--->target與mid同在左半區,繼續常規二分即可若mid在右半區:nums[mid] < target && target < nums[right]--->target與mid同在右半區,繼續常規二分即可若表達式不成立,則無法確定target所在半區,則淘汰無效部分重新判斷注意事項:由于未真正找到數組兩半區如何劃分,當target所在分區確定后,原本判斷target所處獨立分區的代碼功能會退化為常規二分,稍顯冗余無法避免*/public int search(int[] nums, int target) {//雙指針置于有效部分兩端int left = 0, right = nums.length - 1;while(left <= right) {int mid = (left + right) >>> 1;//找到目標值if(target == nums[mid]) {return mid;}//判斷mid所在區間if(nums[left] <= nums[mid]) { //mid在左半區//判斷target所在區間if(nums[left] <= target && target < nums[mid]) { //target必定在左半區right = mid - 1; //淘汰無效部分,后續為常規二分} else { //無法確定target所在半區left = mid + 1; //淘汰無效部分,重新判斷(不在 left -> mid之間)}} else { //mid在右半區if(nums[mid] < target && target <= nums[right]) { //target必定在右半區left = mid + 1; //淘汰無效部分,后續為常規二分} else { //無法確定target所在分區right = mid - 1; //淘汰無效部分,重新判斷(不在 mid -> right之間)}}}return -1;}
}