二分查找----4.搜索旋转排序数组

题目链接

/**

        升序数组在某个位置被分割为前后两部分,前后两部分整体互换;在被改变后的数组中找到目标值

        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;}
}