LeetCode-二分查找

一. 二分查找

​ 二分查找是算法里很常见的一道题目。有的题目直接就是要求二分查找，有的题目是子步骤需要用到查找，而这一块也可以用到二分法进行查找。同时二分法具备的时间复杂度为O(logN)，是一个非常高效的算法。概念很简单，对于有序 的数组，就是一直使用中点mid 进行筛选，逐步缩小区间大小，最后得到答案。但是概念大家都懂，实际操作的时候却发现总是会出现问题，比如判定条件到底是left < right还是left <= right？里面的else if到底是left = mid还是left = mid + 1等等？最后返回的是left还是left + 1？这使得原本觉得二分法很简单的我们，渐渐地发现：原来我们只会做最基本的那个二分查找，只要稍微加一点变动，就很容易出现纰漏。所以这里就是要好好总结二分查找的真实框架，真正地掌握二分查找的精髓，而不是只会做那道最简单的二分查找。

​ 本文参考链接：《二分查找算法细节详解》，《Leetcode题解 - 二分查找》

二. LeetCode 704. 二分查找

题目描述：给定一个升序的整型数组nums和一个目标值target，假设nums中所有的元素是不重复的，使用二分法找到目标值的index。如果不存在，返回-1。 题目链接

分析：这就是最简单的二分查找题，升序，元素不重复，目标就是找到target值。很容易就能写出代码。

代码：

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;	// 可以防止int溢出
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] > target)
                right = mid - 1;
            else
                left = mid + 1;
        }
        return -1;
    }
}

代码分析：

①首先是赋值，为什么是nums.length - 1？因为我们要寻找的是具体的数组元素，这个是最后一个元素的index。

②循环结束条件为什么是 left <= right？这时候直接思考，循环什么时候才该结束？如果找到了target值，也就是nums[mid == target]，毫无疑问就直接return了。那如果没有找到呢？也就是搜索区间为空。最开始的搜索范围是[0, nums.length - 1]，那么当left == right的时候，此时搜索范围为[left, left]，也就是搜索区间非空，因此等于的时候，循环还未结束。（最简单的思路，如果只有一个元素，此时left == right，直接跳出循环，导致稳定返回-1，而没有考虑那个唯一的元素是否等于target值）

③为什么else if里面是right = mid - 1，left = mid + 1？有的代码却是直接right = mid，或者left = mid。最关键的就是要明确搜索空间，最开始我们的搜索空间是[left, right]，既然都已经知道了nums[mid] != target，那么下一个的搜索区间应该是什么？显然，完全不用再考虑mid这个位置，所以下一步的搜索空间应该为[left, mid - 1]，或者[mid + 1, right]。只要明确这个搜索空间的变化，那么left跟right的变化就会很清晰。

④这个算法很容易写出来，哪怕把判定条件去掉等号，只要在最后return的时候再加一个特殊处理也可以。那么这个算法的局限性是什么，当我们的二分查找稍微改变一下，这个代码就不能work。比如，如果数组里存在重复的元素，而且我们想要找到target值的第一个index，或者是最右边的index，这时候应该怎么做？如果继续套用这个最简单的二分模板而不加以改动，我们能做的只是，找到一个target，然后再向左向右进行线性查找。这确实是最容易想到的办法，但是在特定的情况下，也会导致二分查找的时间复杂度从O(logN)退化成O(N)，这并不可取。所以这段代码并不是银弹，也因此二分查找并不是不需要思考就能随便解决的问题，根据不同的情况，初始化，循环条件，left跟right的改变，都是会发生变化的。

三. LeetCode 34. 寻找左&右侧边界的二分搜索

Ⅰ. 题目描述：

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。你的算法时间复杂度必须是 O(log n) 级别。如果数组中不存在目标值，返回 [-1, -1]

题目链接

---

Ⅱ. 分析：

根据上一题最后的代码分析，我们知道，上一题的代码在这里行不通。从上一题得知，二分查找的关键是：清晰搜索区间，以及搜索区间 的变化。这道题最关键的一点，我们不能直接在找到target之后结束，而是应该继续缩小搜索空间。

正如我们上一题所提到的二分查找的各种要点，它们之间也是会互相影响的（根据逻辑而驱动）。

①right的赋值是nums.length - 1还是nums.length，实际上right并不只是一个简单的初始值，它代表的是右区间，决定了我们是搜索区间 是[left, right] 还是[left, right)。

②if，else if的逻辑中，left，right的调整，是由题意以及第①点所一起影响的。如果是像第一题一样简单，那么如果匹配到target，显然就直接return，而如果是找左边界右边界，就要继续缩小搜索空间。else if中left跟right的改变，也与搜索空间的全闭区间还是左闭右开区间有关（主要体现在是否+1，-1）。

③循环条件的结束，也是根据搜索区间的开闭情况，具体情况来决定，返回值则要根据if，else的逻辑判断。

---

Ⅲ. 二分法的关键：

如果你直接去看上面的LeetCode题解，看了labuladong的题解，你会有一种豁然开朗的感觉，原来二分法有这么多details，原来这就是为什么二分法看似简单，实际上总是容易出错。而且也许你还会自豪地认为：原来搜索target的第一个位置跟最后一个位置是这样解决的，感觉自己对于二分法已经了如指掌。我一开始也是这么想的，直到我自己亲手写这篇文章，我才发现了更多的问题。labuladong的题解，清楚地阐述了：搜索区间，循环结束条件，初始化导致的开闭区间，if跟else if的变化，看着标准的代码，然后进行解释，确实很有效，也很好理解。那么问题来了，当我们最开始写的代码的时候，如何确定初始化是nums.length还是nums.length - 1?到底搜索区间是闭区间还是开区间？if跟else if一定要这样写吗，有没有其他的写法？因为我们的目标是生成代码，写出正确的代码，而不是看懂答案。

答案很简单，labuladong大佬的题解，也已经提到了，但没有明确地说出来。实际上结果就是，赋值成nums.length是可行的，赋值成nums.length - 1也同样可行，开区间，闭区间，都是可行的，只是在不同的情况下，会导致你if跟else的变化也不一样（可能+1，可能-1，可能不加不减）。所以关键就是：明确搜索区间的意义。接下来用具体的例子来阐述不同题目中搜索区间的意义，以及变化，紧接着如何编码。

---

Ⅳ. 左边界的情况（ target的第一个位置 )

①right赋值成nums.length，区间的实质意义是左闭右开的情况：

int left_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0;
    int right = nums.length; // 注意
    
    while (left < right) { // 注意
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid; // 注意
        }
    }
    return nums[left] == target ? left : -1;
}

right初始化为nums.length，表明它代表的区间是左闭右开，也就是[left, right)。那么循环条件是否有等号？假设left == right，此时的搜索区间是[left, left)，为空区间，显然应该已经结束，所以循环结束的判定条件是left < right。

而第一个if语句，因为我们要继续往左边搜索（搜索左边界），所以就是right = mid（因为右区间是开区间，所以不需要-1）。然后第一个else if语句，如果mid的元素比target小，left = mid + 1，搜索区间往右边搜索，同时要排除mid，很好理解。接着是第二个else if语句（实际上写成else也可以，理解就行），mid的元素比target大，那么就是要区间往左边搜索，实际上情况是跟相等的时候一样的，也是因为开区间，所以无须考虑-1。

最后循环结束的时候，left == right，所以返回left还是right都是一样的。那么到底要不要+1，-1？在我们最后一次 执行nums[mid] >= target的时候，实际上也就是nums[mid] == target，所以这时候的mid就已经是answer，而且right == answer，后面一直修改的都是left的值，直到left == right，循环结束。所以最后直接返回left或者right即可。

②right赋值为nums.length - 1，也就是两边都是闭区间。

public int searchRange(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;	// 可以防止int溢出
            if (nums[mid] == target)
                right = mid - 1;
            else if (nums[mid] > target)
                right = mid - 1;
            else
                left = mid + 1;
        }
        if (right + 1 >= nums.length || nums[right + 1] != target)
            return -1;
        return right + 1;
    }

因为是闭区间，所以循环判定条件是left <= right，否则当left == right的时候，搜索区间为[left, left]，并非空区间，这样搜索毫无意义，而且如果在if跟else语句的判定中有问题，那么还会出现死循环的情况。

第一个if语句，跟①的开区间有什么区别？right = mid - 1，因为它是闭区间，而非开区间，所以要把mid给pass掉。而当mid元素大于target的时候，同样如此，因为要把搜索区间往左边逼近，那么就是修改right。而当mid元素小于target时，是往右边逼近，则修改left，+1同样是为了排除掉mid。

循环结束，为什么是right + 1？其实最后的循环结束条件是left == right + 1，所以这里return left也是完全可行的。同样地，在最后一次 执行nums[mid] >= target的时候，也必定是在执行nums[mid] == target，所以这时候的mid就是answer，即right == mid - 1，后续都是对left进行修改，直到循环结束。所以最后返回的值是right + 1，或者left。

---

Ⅴ. 右边界的情况 （ target的最后一个位置 ）

其实跟左边界是一样的，关键都是理清楚搜索区间的实质含义。

①right赋值为nums.length，也就是区间为左闭右开的情况。

int right_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0, right = nums.length;
    
    while (left < right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            left = mid + 1; // 注意
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    return left - 1; // 注意
}

因为我们要找右边界，所以nums[mid] <= target的时候，都是要向右逼近区间，因为左区间是闭区间，所以要去掉mid，也就是left = mid + 1。而当nums[mid] > target，要向左逼近区间，因为右区间是开区间，所以直接right = mid就已经去掉了mid。

循环结束条件是left == right，而在我们最后一次执行nums[mid] <= target逻辑的时候，这时候左区间left，实际上就已经是右边界的右一位，之后的操作都是操作right，直到循环结束。所以执行最后一次 left = mid + 1，实际上就是执行最后一次nums[mid] == target，这时候的mid就是最终的答案，而left一直没有变化，也就是left == answer + 1，后面修改的都是right。所以最后返回的就是left - 1。当然，因为最后的时候left == right，所以返回right - 1也是完全一样的。

②right赋值为nums.length - 1，也就是左右区间均为闭区间的情况

public int searchRange(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;	// 可以防止int溢出
            if (nums[mid] == target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid - 1;
            else
                left = mid + 1;
        }
    	if (right >= nums.length || nums[right] != target)
            return -1;
        return right;
    }

因为是闭区间，所以循环结束条件是left <= right，不再赘述。而当nums[mid] <= target的时候，区间向右逼近，并且要把mid排除在外，所以操作是left = mid + 1。而当nums[mid] > target的时候，区间向左逼近，并且要把mid排除在外，因为右区间也是闭区间，所以操作是right = mid - 1。

最后的返回值，在我们最后一次 执行nums[mid] <= target的时候，最后一次一定是nums[mid] ==target，也就是这时候的mid就是answer，即left = answer + 1，后面修改的都是right的值，直到循环结束。循环结束的时候，left = right + 1，所以我们可以返回left - 1，也可以返回right。

Ⅵ. 总结

​ 通过这一题的分析，可以很清晰地体会到二分法的解法关键。搜索区间的变法是二分法的关键，我们首先要确定定义的搜索区间究竟是开区间还是闭区间，进而在不同的情况下，修改 left跟 right的情况也有所不同（开区间与闭区间，会决定是否需要+1，-1等）。而最后的返回值，关键就是最后一次执行nums[mid] == target，实际上这时候的mid就是最后的返回值，只要清晰这一点，返回值就能直接得出来，而不是靠猜测。

---

四. LeetCode 69. 求x的平方根

69.Sqrt(x) (Easy)

Leetcode / 力扣

题目描述：实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

分析：这道题可以直接暴力法解决，因为Integer.MAX_VALUE的平方根是46340，所以直接寻找0~46340即可，但要注意的是小心int溢出导致的死循环。不过这是因为这道题的范围比较小，如果范围较大，那么这个O(n)的解法并不算特别好。实际上这道题也可以转换成标准的二分法题目：“一个有序数组，数值0 ~ 46341，寻找一个值x，使得x的平方等于target，此时返回x。或者x`的平方大于target，此时返回最小的x`。

代码：

①暴力法:

class Solution {
    public int mySqrt(int x) {
        int temp = 0;
        while (temp <= 46340) {
            if (x < temp * temp)
                return temp - 1;
            if (x == temp * temp)
                return temp;
            temp++;
        }
        return temp - 1;
    }
}

PS:对于46340这个数，如果我们不知道Integer.MAX_VALUE的平方根，也可以换一种写法，循环条件变成true，也就是无限循环，而当temp * temp < 0，也就是数值溢出的时候，跳出循环即可。改法很简单，不再赘述。这一题使用暴力法的执行用时为22ms，可以看到是很慢的。

②二分法：

class Solution {
    public int mySqrt(int x) {
        int left = 0, right = 100000;
        while (left <= right) {
            int mid = (left + right) / 2;
            int tmp = mid * mid;
            if (tmp == x)
                return mid;
            else if (tmp > x || tmp < 0)
                right = mid - 1;
            else
                left = mid + 1;
        }
        return right;
    }
}

PS:二分法因为时间复杂度很低，为O(logN)，所以右边界为100000，还是46341，区别可以忽略不计。二分的逻辑也不难，关键是最后tmp > x || tmp < 0处，这时候表明mid是最后（也是最左）使得mid的平方大于x的数，所以此时的mid - 1就是answer1，即right == mid- 1 == answer，之后的所有操作都是对left进行操作，或者直接出现tmp == x的逻辑使得直接返回真正的answer。无论如何，当后续没有进入tmp == x的逻辑，说明就是只对left进行修改，而right并没有修改，所以right = answer，所以可以返回right。当然，循环结束时，left == right + 1，所以返回left - 1也是一样的。此题使用二分法的执行用时为1ms。

---

五. LeetCode 744. 大于给定元素的最小元素

744.Find Smallest Letter Greater Than Target (Easy)

Leetcode / 力扣

Input:
letters = ["c", "f", "j"]
target = "d"
Output: "f"

Input:
letters = ["c", "f", "j"]
target = "k"
Output: "c"

题目描述：给定一个只包含小写字母的有序数组letters 和一个目标字母 target，寻找有序数组里面比目标字母大的最小字母。

数组里字母的顺序是循环的。举个例子，如果目标字母target = ‘z’ 并且有序数组为 letters = [‘a’, ‘b’]，则答案返回 ‘a’。

分析：有序数组中找target，标准的二分法套路可以解决。这道题的评论里存在钻牛角尖的情况，关于“数组里字母的顺序是循环的。”这句话，英语原文是“Letters also wrap around. ”，实际上意思是指，当 target比数组里最大的元素还要大（或者相等），那就直接返回数组里最小的元素，而并不是 z < a < b有序。

如果你真的想这么排，那么还叫什么有序数组呢？[z, a, b, c, z, b, a]也是一个“有序数组”，因为z < a < b < … < z。而为什么b又小于a？b < c < d < … < z < a。如果你把这称为有序，那这个有序又有什么意义呢。如果拿33题来类比，33题是说一个有序数组，旋转了一次变成了“Rotated Sorted Array”，但这个数组并不是有序数组。总而言之，这道题就是简单的二分法，不用想太多warp around。

代码：

class Solution {
    public char nextGreatestLetter(char[] letters, char target) {
        int left = 0, right = letters.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (letters[mid] <= target)
                left = mid + 1;         // 区间向右寻找
            else
                right = mid - 1;        // 区间向左寻找
        }
        return left < letters.length && letters[right + 1] > target ?
            letters[right + 1] : letters[0];
    }
}

代码分析：直接选择闭区间（开闭区间只影响了一下±1，只要清晰搜索区间的变化即可，不再赘述！），然后letters[mid] <= target的时候，区间都是向右缩小，所以可以写在一起，当然最开始不熟练的时候可以写成if跟else if，逻辑更加清晰。而letters[mid] > target的时候，区间向左缩小。循环结束的时候，left = right + 1，所以最后的返回，使用left或者right + 1都是一样的，这里为了演示，也是直接在return语句里同时使用了这两个变量，可以随意更改。至于为什么最后是return这个值？同样的，最后一次执行right = mid + 1的时候，此时的mid就是answer，即right = answer - 1，后续都是对left进行改变，所以最后的asnwer就是right + 1。同时题目里还有其他要求，如果数组里没有比target更大的元素，则返回最小的元素，所以还加了一些判定。

---

六. LeetCode 540. 有序数组的唯一元素

540.Single Element in a Sorted Array (Medium)

Leetcode / 力扣

Input: [1, 1, 2, 3, 3, 4, 4, 8, 8]
Output: 2

题目描述：给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。您的方案应该在 O(log n)时间复杂度和 O(1)空间复杂度中运行。

分析：在有序数组里寻找元素，同时要求时间复杂度为O(logN)，显然就是需要使用二分法。二分法依然是对搜索区间的缩小逼近，最后找出结果。而这道题跟前面的题有点不一样，如果想直接套用前面的思路，都无法通过。其实这道题还有一个信息：我们要找的是只出现一次的元素，并且其他的元素都会出现两次。我们很容易会忽略掉这个信息：”其他元素都会出现两次。“，而这就是这道题使用二分法的关键。

当我们使用mid对数组一分为二之后，之后的第一步操作很容易想到，看mid是否与mid - 1或者mid + 1相等，如果都不相等，那么显然就是直接返回nums[mid]，同时还要注意一下边界情况，以防数组边界溢出。那么当确定mid不是唯一元素之后，应该如何缩小搜索区间？这时候就要用到其他元素都会出现两次 这个信息，通过判定左右区间的元素数量是奇数还是偶数 来判断唯一元素的位置。同时还要考虑与 mid相等的值，到底是mid - 1，还是mid + 1。使用变量isLeft来记录与mid相等的值，true表示nums[mid - 1],false表示nums[mid + 1]。使用变量leftEven来记录左边区间的数量奇偶情况，true表示偶数，false表示奇数。

①相等的值是nums[mid - 1]，左区间数量是偶数，即 isLeft == true && leftEven == true

左边数量是偶数，但左边有一个与mid相同的值，去掉这个，剩下的是奇数，显然，唯一值就在左边的区间。

②相等的值是nums[mid + 1]，左区间数量是奇数，即isLeft == false && leftEven == false

左边数量是奇数，并且与mid相同的值在右边，说明唯一值就在左边的区间。

③其他情况

不在左区间，又不是mid，当然就在右区间。

除此之外，left跟right的变化也不是简单的left = mid - 1或者right = mid + 1，比如情况①，如果是简单的right = mid - 1，会出现什么错误？这时候的搜索区间是[left, mid - 1]，而右区间已经被我们丢弃掉，此时的nums[mid - 1]，显然不是正确答案，但在这一块区间里，它只有一个值，这会成为后续二分的一个误导项。所以正确的修改搜索区间的方法应该是：当要搜索左区间，并且与mid相等的值在左边（即mid - 1），那么此时应该是right = mid - 2，而与mid相等的值在右边才是right = mid - 1。右区间同理，不再赘述。

代码：

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (mid == 0 || mid == nums.length - 1)
                return nums[mid];
            boolean isLeft = false;
            if (nums[mid - 1] == nums[mid])
                isLeft = true;
            else if (nums[mid + 1] == nums[mid])
                isLeft = false;
            else
                return nums[mid];
            boolean leftEven = (mid - left) % 2 == 0;    // 不考虑mid
            if (isLeft && leftEven)
                right = mid - 2;
            else if (!isLeft && !leftEven)
                right = mid - 1;
            else if (isLeft)
                left = mid + 1;
            else
                left = mid + 2;
        }
        return nums[left];
    }
}

---

七. LeetCode 153. 寻找旋转排序数组中的最小数字

题目描述：假设按照升序排序的数组在预先未知的某个点上进行了旋转。

Leetcode / 力扣

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。

你可以假设数组中不存在重复元素。

分析：虽然旋转了一次之后，数组不再是有序数组，但是还是具备相当多的”有序特征“，所以依然可以使用二分法来快速寻找数字。关键是mid元素应该如何判断进而改变搜索区间？mid元素跟谁比较，left还是right？

我们先尝试将nums[mid]与nums[left]比较，原本的有序数组中，nums[left] < nums[mid]，因此如果旋转后依然如此，也不能看出任何特别（到底是nums[left]还是nums[mid + X]更小？无法判断），因此这个方案pass。

接着尝试将nums[mid]与nums[right]比较，原本的有序数组中，nums[mid] < nums[right]，所以如果旋转后依然如此应该怎么办？答案是直接把区间向左缩小，同时要保留这个mid，因为有可能它就是最小数，即right = mid。所以即使跟原来的情况相同，依然能缩小区间，合理可行。（而与nums[left]比较，无法对区间优化）

然后如果旋转后的情况是nums[mid] > nums[right]，此时应该怎么办？显然，这时候右区间就是存在被旋转的数字，而最小数字一定在被旋转的部分上，所以这时候就可以把区间向右逼近，并且毫无疑问地，nums[mid]不是最小数，所以此时的操作应该是left = mid + 1。如此反复，区间越来越小，同时最小的数字并不会被排除在搜索区间之外（因为right = mid，我们没有把比较小的数排除掉）。直到最后，区间留下的最后一个数就是最小数，也就是搜索区间此时为[left, right],并且left == right，所以循环结束条件为left < right。

代码：

class Solution {
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] > nums[right])
                left = mid + 1;
            else
                right = mid;
        }
        return nums[left];      // left == right
    }
}

---

八. LeetCode 33. 搜索旋转排序数组

题目描述：假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。

题目链接

分析：跟上一题一样，虽然不完全是完整的有序数组，但也可以使用二分法来进行搜索。先判断nums[mid]是否就是target，然后再进行讨论，如果nums[mid] < target，正常情况下，可以直接向右区间进行逼近，但这时候其实还有一种情况，这个nums[mid]是旋转部分，这时候target有可能在左，也有可能在右，即下一个搜索区间可能是[left, mid - 1]，也可能是[mid + 1, right]。而当nums[mid] > target，同样也是两个区间都有可能，即[left, mid - 1]或者[mid + 1, right]。可以看到下面的第一版代码，我还考虑什么情况下一定是在其中一个区间，不用考虑另一个区间。但由于二分法的效率非常高，所以直接一刀切也可以，代码也会变得非常简便。

代码：

class Solution {
    public int search(int[] nums, int target) {
        return helper(nums, target, 0, nums.length - 1);
    }

    public int helper(int[] nums, int target, int left, int right) {
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) 
                return mid;
            else if (nums[mid] < target) {
                if (nums[mid] > nums[left])
                    left = mid + 1;     // 右区间
                else
                    return Math.max(helper(nums, target, left, mid - 1),
                                    helper(nums, target, mid + 1, right));
            }
            else 
                return Math.max(helper(nums, target, left, mid - 1),
                                helper(nums, target, mid + 1, right));
        }
        return -1;
    }
}

简化后的代码：

class Solution {
    public int search(int[] nums, int target) {
        return helper(nums, target, 0, nums.length - 1);
    }

    public int helper(int[] nums, int target, int left, int right) {
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) 
                return mid;
            return Math.max(helper(nums, target, left, mid - 1),
                            helper(nums, target, mid + 1, right));
        }
        return -1;
    }
}

---

九. 总结

​ 二分法一开始会觉得很难，但只要你仔细地推导完上面的题目，那么基本就能理解二分法的要义。二分法的关键是搜索区间，而有时候初始的赋值可能是nums.length - 1，也可能是nums.length，这会导致区间到底是开区间还是闭区间，实际上只要明确搜索区间的含义 即可。至于后面是否+1，-1，只要你清晰是否要排除mid，开区间还是闭区间，导致的下一个搜索区间 到底是什么，这样就能明确是否要±1，而不是混乱不清。循环结束条件也不是一成不变的，并不是说开区间就没有等号，而闭区间就有等号，还是要具体题目具体分析。而最后的返回值，一开始可能会觉得很麻烦，实际上搜索区间的变化 是有迹可循的，前面可能是left跟right都会变化，而在某一次循环，就会导致left或者right发生变化，这时候的mid基本就与answer有关，而后续都是另一个变量一直变化，无限缩小区间，直到循环结束。然后根据那次某变量最后的变化 ，得出answer与left / right的关系，那就是最后的结果。