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

搜索旋转排序数组

例如&＃xff0c; [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target &＃xff0c;如果 nums 中存在这个目标值 target &＃xff0c;则返回它的下标&＃xff0c;否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

是一个比较传统的二分查找的模式

首先需要将一个数组每次都进行拆分&＃xff0c;有题意可知&＃xff0c;我们的数组需要分为两个情况。

1. 将中间值nums[mid]和nums[0]比较大小 分为两种情况
2. 将中间值nums[mid]和nums[n-1]比较大小 分为两种情况

以上的分法都可以
都可以进行有效拆分
比如由于我们mid 的写法 int mid &＃61; l &＃43; ((r-l)>>>1);一定靠左
如果使用1. 将中间值nums[mid]和nums[0]比较大小 &＃xff1a;就需要 nums[0]<&＃61;nums[mid]
如果使用2. 将中间值nums[mid]和nums[n-1]比较大小 &＃xff1a;就需要 nums[n] 先以第一种情况为例

public static int search(int[] nums, int target) {int l &＃61; 0 ,n &＃61; nums.length-1, r &＃61; n;while(l<&＃61;r){int mid &＃61; l &＃43; ((r-l)>>>1);if (nums[mid]&＃61;&＃61;target){return mid;}if (nums[0] <&＃61; nums[mid]) {if (nums[0] <&＃61; target && target < nums[mid]) {r &＃61; mid - 1;} else {l &＃61; mid &＃43; 1;}} else {if (nums[mid] < target && target <&＃61; nums[n]) {l &＃61; mid &＃43; 1;} else {r &＃61; mid - 1;}}}return -1;}


如有错误欢迎指正