二分查找3

1. 有序数组中的单一元素（540）

题目描述：

算法原理：
二分查找解题关键就在于去找到数组的二段性，这里数组的二段性是从单个数字a开始出现然后分隔出来的，如果mid落入左半部分那么当mid为偶数时nums[mid+1]等于nums[mid]，当mid为奇数时nums[mid]等于nums[mid-1]，mid落入右半部分则相反。
细节：
循环内的判断条件首先需要判断mid是偶数还是奇数，接着还要判断相等的关系，是比较麻烦的。我们发现规律当mid为偶数异或1时就会得到mid+1，当mid为奇数异或1时就会得到mid-1，因此我们的判断条件直接简化为nums[mid]是否等于nums[mid^1]。
代码如下：

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

题目链接

2. 寻找旋转排序数组中的最小值 II（154）

题目描述：

算法原理：
nums数组的二段性体现在nums[right]，前半部分旋转过去的值是大于等于nums[right]的，后半部分的值都是小于等于nums[right]。不过这题需要注意的地方就是因为数值是可以重复的，所以当nums[mid]等于nums[right]的时候我们是不知道mid是落在前半部分还是后半部分的，为了解决这种情况我们直接将right向左移动一位即可，移动之后因为我们求的是最小值，所以不会影响结果，并且达到了一种去重的效果。
代码如下：

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

题目链接

3. 搜索二维矩阵（74）

题目描述：

算法原理：
这一题可以使用朴素二分查找的思想来解决，将多维数组看作一维的数组，此时铺开来left=0、right=m*n-1，得到的mid位置的值在二维数组中可以表示为matrix[mid/n]matrix[mid%n]，这里的m就是数组的维度数，n就是每个维度的元素个数。
代码如下：

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int left = 0, right = m * n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (matrix[mid / n][mid % n] > target) {
                right = mid - 1;
            } else if (matrix[mid / n][mid % n] < target) {
                left = mid + 1;
            } else {
                return true;
            }
        }
        return false;
    }
}

题目链接