算法训练——二分法算法（LeetCodeHOT100）

摘要

300. 最长递增子序列

287. 寻找重复数

class Solution {
    public int findDuplicate(int[] nums) {
         int slow = 0, fast = 0;
        //第一次想遇的时候
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);
        fast = 0;
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        // 快慢指针想遇
        return fast;
    }
}

240. 搜索二维矩阵 II

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int len=matrix.length;
        int row=matrix[0].length;
        int x=0,y=row-1;
        while(x=0){
            if(matrix[x][y]==target){
                return true;
            }
            if(matrix[x][y] taget 还是的nums[mid]< target
            if (nums[mid] > target || (lower && nums[mid] >= target)) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}

33. 搜索旋转排序数组

对于有序数组，可以使用二分查找的方法查找元素。但是这道题中，数组本身不是有序的，进行旋转后只保证了数组的局部是有序的，这还能进行二分查找吗？答案是可以的。

可以发现的是，我们将数组从中间分开成左右两部分的时候，一定有一部分的数组是有序的。拿示例来看，我们从 6 这个位置分开以后数组变成了 [4, 5, 6] 和 [7, 0, 1, 2] 两个部分，其中左边 [4, 5, 6] 这个部分的数组是有序的，其他也是如此。

这启示我们可以在常规二分查找的时候查看当前 mid 为分割位置分割出来的两个部分 [l, mid] 和 [mid + 1, r] 哪个部分是有序的，并根据有序的那个部分确定我们该如何改变二分查找的上下界，因为我们能够根据有序的那部分判断出 target 在不在这个部分：

如果 [l, mid - 1] 是有序数组，且 target 的大小满足 [nums[l],nums[mid])，则我们应该将搜索范围缩小至 [l, mid - 1]，否则在 [mid + 1, r] 中寻找。 如果 [mid, r] 是有序数组，且 target 的大小满足 (nums[mid+1],nums[r]]，则我们应该将搜索范围缩小至 [mid + 1, r]，否则在 [l, mid - 1] 中寻找。

package 二分法;

import org.junit.Test;

public class search33 {
    /**
     * 这也是一个变形的二分法
     * 利用的暴力的算法是的遍历
     * 

     * 通过的判断 左边断电和右端点的来比较
     *
     * @param nums
     * @param target
     * @return
     */
    public int search(int[] nums, int target) {
        int n = nums.length;
        // 当没有数据的时候
        if (n == 0) {
            return -1;
        }
        // 当只有一个数据的时候
        if (n == 1) {
            return nums[0] == target ? 0 : -1;
        }
        int l = 0, r = n - 1;
        // 二分法
        while (l > 1;
            if (nums[mid] == target) {
                return mid;
            }
            // 判断左边和中间的值
            if (nums[0]