这题本质上还是二分查找，只是数组被“旋转”了。
正常二分里，数组整体有序。
但这里：
[4,5,6,7,0,1,2]整体不是有序的。
不过有个非常关键的性质：
每次二分后，左右两边一定有一边是有序的。
这就是突破口。
一、核心思路
每次取中点：
mid = (left + right) / 2然后判断：
nums[left] <= nums[mid]如果成立：
说明左半边有序
否则：
说明右半边有序
然后看target是否落在有序区间内。
二、举例彻底理解
数组：
[4,5,6,7,0,1,2]target = 0
第一次
left = 0 -> 4 right = 6 -> 2 mid = 3 -> 7现在：
4 5 6 7 | 0 1 2看：
nums[left] <= nums[mid] 4 <= 7成立。
说明：
左边 [4,5,6,7] 有序然后判断：
target=0 是否在：
[4,7]之间。
显然不在。
所以：
去右边找即：
left = mid + 1第二次
现在：
0 1 2即：
left = 4 right = 6 mid = 5 nums[mid] = 1看：
nums[left] <= nums[mid] 0 <= 1成立。
说明：
左边 [0,1] 有序target=0 是否在：
[0,1]之间？
在。
所以：
去左边继续二分即：
right = mid - 1第三次
left = 4 right = 4 mid = 4发现：
nums[mid] == target返回 4。
三、最重要的理解
旋转数组虽然整体无序：
4 5 6 7 0 1 2但它一定是：
一段升序 + 一段升序所以：
每次二分后，一定至少有一边是完全有序的。
我们就利用这一边判断 target 在不在里面。
四、代码（最经典写法）
class Solution { public int longestValidParentheses(String s) { int max = 0; int[] dp = new int[s.length()]; for (int i = 1; i < s.length(); i++) { if (s.charAt(i) == ')') { // 1. () if (s.charAt(i - 1) == '(') { dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2; } // 2. )) else if (i - dp[i - 1] - 1 >= 0 && s.charAt(i - dp[i - 1] - 1) == '(') { dp[i] = dp[i - 1] + 2; if (i - dp[i - 1] - 2 >= 0) { dp[i] += dp[i - dp[i - 1] - 2]; } } max = Math.max(max, dp[i]); } } return max; } }五、你真正需要记住的只有两句话
1. 判断哪边有序
nums[left] <= nums[mid]成立：
左边有序否则：
右边有序2. 判断 target 在不在有序区间
左边有序：
nums[left] <= target && target < nums[mid]右边有序：
nums[mid] < target && target <= nums[right]六、为什么时间复杂度还是 O(log n)
因为每次都：
砍掉一半区间所以仍然是二分查找。
这题是二分查找里非常经典的一道“变形题”。
你如果已经会普通二分，这题真正难的点只有：
“每次一定有一半有序”
一旦理解这一点，后面就是普通二分逻辑了。
建模方法)
