题目链接
/**
升序数组在某个位置被分割为前后两部分,前后两部分整体互换;在被改变后的数组中找到目标值
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;}
}
