leetCode ✏基础刷题之(81. Search in Rotated Sorted Array II)
.
✏描述
假设已升序排序的数组在某个位置上发生了旋转,给定一个目标数,查找这个数是否存在数组中,这道题最大的不同在于可能数组中存在重复值.
✏题目实例
✏题目分析
这道题可以使用二分查找去解题,之前写过一个二分查找好用的模板文章,具体地址请移步 https://mp.weixin.qq.com/s?__biz=MzU3Mzc5NTU2MQ==&mid=2247484785&idx=1&sn=4daaf34c9714ff3388fc4a4ad4190728&chksm=fd3d78f7ca4af1e1be14c1c1ca9bd220a74512528e74caed853bf5eb7b3877837fabcb1411c0&token=889524492&lang=zh_CN#rd
这是第一版不存在重复值:https://github.com/wuqinqiang/leetcode-php/blob/master/0-50/33.md
只要中间数比最右边的还小，说明右边是有序的，一旦满足目标值大于等于中间数并且小于等于right值，说明目标可能在右边(并且包括中间数)，否则就在左边 并且肯定不包括中间数。反之也是同样的道理。最后再做下尾部处理即可。
✏最终实现代码
/**
* @param Integer[] $nums
* @param Integer $target
* @return Boolean
*/
function search($nums, $target) {
$num=count($nums);
if($nums==0) return false;
$left=0;
$right=$num-1;
while($left<$right){
$middle=($left+$right+1)>>1;
if($nums[$middle]<$nums[$right]){ //右边的一定是顺序数组包括中位数
if($nums[$middle]<=$target && $nums[$right]>=$target){
$left=$middle;
}else{
$right=$middle-1;
}
}else if($nums[$middle]>$nums[$right]){ //左边数顺序 包括中位数
if($nums[$left]<=$target && $target<$nums[$middle]){
$right=$middle-1;
}else{
$left=$middle;
}
}
else{
if($nums[$right]==$target) return true;
$right--;
}
}
return $nums[$left]==$target;
}
转载链接：https://leetcode.cn/
![[爱了]](/js/img/d1.gif)
![[尴尬]](/js/img/d16.gif)