折半查找部分有序

部分有序 本周qq群有人咨询

Search in Rotated Sorted Array 来源： https://leetcode.com/problems/search-in-rotated-sorted-array/ 难度：Difficulty: Hard

题目

Suppose a sorted array is rotated(旋转的) at some pivot unknown to you beforehand(提前的) eg： 0 1 2 3 4 5 6 7 旋转3个might become 4 5 6 7 0 1 2 3. 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.

分析：

观察：

• 举例就用0-9来打比方很容易观察规律
• 7为旋转点两边都是升序 【4 5 6】 【0 1 2 3 】这个问题来了 不清楚应该去那边去寻找方向了 例如寻找3 可能在left 也有可能在right 从7 来看 一个升序 一个降序 都可能 …….. ……. 从这个思路无法判断，你明确表示出来 判断不了，你感觉没问题就是分析不出来呀 然后果断在换个思路 这个我一般不具备 不能在这里死磕 不然陷入了题目给造成的陷阱去了

Q1 有序数组折半是中间位置和查找元素 现在中间位置可以判断出来 查找元素元素方向无法判断如果不匹配是 去left 还是right寻找

我感觉还是判断趋势 假如array[begin end] case 1 0 1 2 3 4 5 6 7 特点：7>0 array[end] > array[begin]升序

case 2 4 5 6 7 0 1 2 3 特点：array[end] < array[begin] 旋转点在中间

是升序 还是降序还是 还是混合都有 我用的根据相 邻2个元素 6 7 0 判断出来了还是解决无法判断呢

Q2一个数组 确定中间位置去判断(相邻元素) 假如是7 left是 升序[4 5 6 7] 你如何判断查找元素3位置 回到问题Q1了 你忘记是有序了 一眼看出3不再这里面呀 3<4<7 回到问题Q1了 A2：为什么那相邻元素呢 为什么不用 array[end]，array[begin] 一个数组假如有拐点 无法判断就不去判断了，继续拆分

如果一个数组不满足判断条件 继续拆分 满足到符合条件为止

步骤

step 1 选择中间位置 此时 数组将一份为二 A,B 一边是完全有序 部分A 一是包含旋转点部分B step 2 完全有序 部分A 查找非常简单 判断查找数据是否在有序数组A中 如果在A中对范围A进行查找 step 3 如果没有A中 对B重复步骤 1 2

coding

class Solution { public: int search(vector& nums, int target) { int begin=0;//开始位置 int end=nums.size()-1;//结束位置

1.   //如果元素个数小于<<2个不适合2.   if(0 ==end )3.   {4.       return target ==nums[0]?0:-1;5.   }6.   if(1 == end )7.   {8.       if(target ==nums[0] ) {return 0;}9.       if(target ==nums[1]) {return 1;}10.       return -1;11.   }12.   while(begin<=end)13.   {    14.        int mid=(end+begin)/2;15.       //find 16.       if( target == nums[mid])17.       {18.           return mid;19.       }20.21.       // 完全有序A |mdi|包含拐点的有序B22.       if(nums[begin]<=nums[mid] )23.       {    //查找数据在完全有序数组A中 只要对数组A进行折半查找24.           if(nums[begin]<=target && target <nums[mid] )25.           {26.               end=mid-1;27.           }else //包含拐点的有序B中28.           {29.               begin=mid+1;30.           }31.       }else32.       { // 包含拐点的有序B|mdi|完全有序A33.34.            if(nums[mid]<target && target <=nums[end] )35.           {36.               begin=mid+1;37.           }else //包含拐点的有序B中38.           {39.              end=mid-1;40.           }41.       }42.   }43.44.   return -1;//not find 45.}

};

验证:

代码错误 <= 写成 << 不是比较运算符了 if(nums[begin]<<target && target<nums[mid] ) 改为 nums[begin]<=target

[5,1] 最后两个元素分隔时候 if(nums[begin]<nums[mid] ) 改为 if(nums[begin]<=nums[mid] )

难点:

当中间元素和查找元素不相等时候 如何确定查找元素范围 ->通过通过比较中间元素 和开始和结束位置 确定完全有序范围 -> 从而推断查找元素范围