LeetCode入门指南 之 二分搜索

上图表示常用的二分查找模板：

第一种是最基础的，查找区间左右都为闭区间，比较后若不等，剩余区间都不会再包含mid；一般在不需要确定目标值的边界时，用此法即可。

第二种查找区间为左闭右开，要确定target左边界时，若nums[mid] == target，取right = mid：

int left = 0; 
int right = arr.length;	//注意

while (left < right) {	//注意
    //相比 mid = (left + right) / 2的写法可以防止越界
    int mid = left + (right - left) / 2; 
    if (arr[mid] == target) {
        //向左查找边界
        right = mid;
    } else if (arr[mid] < target) {
        left = mid + 1;
    } else if (arr[mid] > target) {
        right = mid;
    }   
}

/**
  * 跳出循环时，left=right；left对应元素可能为target。
  * 当target若大于所有元素，退出循环时有left=right=nums.length。故最后需要判断left是否越界以及left对应元素是否为target
  */
if (left >= arr.length) return -1;		//target比所有元素都大（没找到），此时表示小于target的元素有left个
if (arr[left] != target) return -1;	//（没找到）此时表示小于target的元素有left个

return left;	//left为target的左边界，表示小于target的元素有left个。可知，若没找到target，left为target该顺序插入的位置。

要确定target右边界时，若nums[mid] == target，取left = mid + 1:

int left = 0; 
int right = arr.length; //注意

while (left < right) {	//注意
    int mid = left + (right - left) / 2;
    if (arr[mid] == target) {
        //向右边界查找
        left = mid + 1;
    } else if (arr[mid] < target) {
        left = mid + 1;
    } else if (arr[mid] > target) {
        right = mid;
    }
}
/**
  * 跳出循环时，left=right；left - 1 对应元素可能为target（比如：只有一个target时，mid指向target，下一步会将left置为mid + 1）；
  * 当target小于所有元素时有left=right=0；故最后需要判断left-1是否越界和left-1对应元素是否为target
  */
if (left - 1 < 0) return -1;
if (arr[left - 1] != target) return -1;

return left - 1;

为什么left = mid + 1 而 right = mid? 这是因为我们的查找区间始终是保持为左闭右开。

重要的来了，如果前面两种你觉得麻烦不好记忆那么你只需要记住第三种即可！第三种最为强大，查找区间左右都为闭区间，比较后若不等，剩余区间都会再包含mid，最后退出时left和right相邻，故都有可能为target。理论上绝大部分场景第三种模板都能解决。

int left = 0; 
int right = arr.length - 1;

while (left + 1 < right) {
    int mid = left + (right - left) / 2;
    if (arr[mid] == target) {
        //向右边界查找；向左边界查找改为 right = mid;
        left = mid;
    } else if (arr[mid] < target) {
        left = mid;
    } else if (arr[mid] > target) {
        right = mid;
    }
}

//判断结果
if (arr[left] == target) {
    return left;
}
if (arr[right] == target) {
    return right;
}

return -1;

61 · 搜索区间

给定一个包含 n 个整数的排序数组，找出给定目标值 target 的起始和结束位置。

如果目标值不在数组中，则返回[-1, -1]

使用模板二：

public class Solution { 
    public int[] searchRange(int[] arr, int target) {
        int left = 0;
        int right = arr.length; //注意左闭右开

        while (left < right) {  //注意
            int mid = left + (right - left) / 2;

            if (arr[mid] == target) {
                //向左查找边界
                right = mid;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else if (arr[mid] > target) {
                right = mid;
            }
        }

        int start = 0;
        if (left >= arr.length) {
            return new int[] {-1, -1};      //没找到
        } else if (arr[left] != target) {
            return new int[] {-1, -1};      //没找到
        } else if (arr[left] == target) {
            start = left;
        }

        left = 0;
        right = arr.length;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (arr[mid] == target) {
                //向右边界查找
                left = mid + 1;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else if (arr[mid] > target) {
                right = mid;
            }
        }

        //这里无需判断是因为查找左边界时已经确定了target存在
        int end = left - 1;	//注意

        return new int[] {start, end};
    }
}

你能尝试用模板三解决吗？

35. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

使用模板三：

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left + 1 < right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] < target) {
                left = mid;
            } else if (nums[mid] > target) {
                right = mid;
            } else if (nums[mid] == target) {
                left = mid;  // 查找左边界
            }
        }
        
        if (nums[left] >= target) return left;
        if (nums[right] >= target) return right;
        // 如果 target 大于所有元素
        if (target > nums[right]) return nums.length;

        return 0;
    }
}

使用模板二：

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length; //注意，左闭右开

        while (left < right) {
            int mid = left + (right - left) / 2;

            //查找target的左边界
            if (nums[mid] == target) {
                right = mid;
            } else if (nums[mid] > target) {
                right = mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            }
        }

        //target的下标（存在时）或小于target的个数
        return left;
    }
}

74. 搜索二维矩阵

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

• 每行中的整数从左到右按升序排列。
• 每行的第一个整数大于前一行的最后一个整数。

使用模板三：将二维转换为一维

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;

        int left = 0;
        int right = m*n - 1;

        while (left + 1 < right) {
            int mid = left + (right - left) / 2;

            int row = mid / n;
            int col = mid % n;

            if (matrix[row][col] == target) {
                return true;
            } else if (matrix[row][col] > target) {
                right = mid;
            } else if (matrix[row][col] < target) {
                left = mid;
            }
        }


        System.out.println(right);
        if (matrix[left / n][left % n] == target) return true;
        if (matrix[right / n][right % n] == target) return true;

        return false;
    }
}

使用模板一：

class Solution {
    //将二维矩阵转化为一维数组
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int left = 0;
        int right = m * n - 1;  //普通二分查找，两边都闭合

        while (left <= right) {
            int mid = left + (right - left) / 2;
            int row = mid / n;
            int col = mid % n;

            if (matrix[row][col] == target) {
                return true;
            } else if (matrix[row][col] > target) {
                right = mid - 1;
            } else if (matrix[row][col] < target) {
                left = mid + 1;
            }
        }

        return false;
    }
}

278. 第一个错误的版本

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

使用模板三：

public class Solution extends VersionControl {
    //思路：T代表争取，F代表错误。给定一个序列 T T T T F F F，查找第一个F下标。二分查找，
    public int firstBadVersion(int n) {
        int left = 1;
        int right = n;  //左右都闭合

        while (left + 1 < right) { //注意
            int mid = left + (right - left) / 2;

            if (isBadVersion(mid)) {
                right = mid;
            } else {
                left = mid;
            }
        }

        if (isBadVersion(left)) {
            return left;
        }
        return right;
    }
}

使用模板二：

public class Solution extends VersionControl {
    //思路：T代表争取，F代表错误。给定一个序列 T T T T F F F，查找第一个F下标。二分查找，
    public int firstBadVersion(int n) {
        long left = 1;
        long right = (long)n + 1;  //左闭右开，改为long，否则2147483647会越界

        while (left < right) {
            int mid = (int) (left + (right - left) / 2);

            //查找左边界
            if (isBadVersion(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return (int)left;
    }
}

153. 寻找旋转排序数组中的最小值

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

• 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
• 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

使用模板三：

class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1; //左闭右开

        while (left + 1 < right) {   //注意
            int mid = left + (right - left) / 2;


            //始终拿 mid 和 right比较
            //在最小值的左边
            if (nums[mid] > nums[right]) {
                left = mid;
            //在最小值的右边
            } else if (nums[mid] < nums[right]) {
                right = mid;
            }
            //没有重复数字的情况下不会出现等于的情况
        }

        if (nums[left] < nums[right]) {
            return nums[left];
        }
        return nums[right];
    }
}

使用模板二：

class Solution {
    public int findMin(int[] nums) {
        int target = nums[nums.length - 1];

        int left = 0;
        int right = nums.length; //注意，左闭右开

        while (left < right) {
            int mid = left + (right - left) / 2;

            //查找左边界
            if (nums[mid] == target) { // 2 3 4 1
                right = mid;
            //在最小值的左边
            } else if (nums[mid] > target) {
                left = mid + 1;
            //在最小值的右边
            } else if (nums[mid] < target) {
                right = mid;
            }
        }

        return nums[left];
    }
}

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

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：

• 若旋转 4 次，则可以得到 [4,5,6,7,0,1,4]
• 若旋转 7 次，则可以得到 [0,1,4,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个可能存在 重复 元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

使用模板三：

class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1; 

        while (left + 1 < right) {
            int mid = left + (right - left) / 2;

            //相等时，你无法确定此时 mid 在最小值的左边还是右边，如：2 2 2 2 2 3 4 2 
            //不用担心 2 为最小值时 right-- 会漏掉最小值，此时 2 总是有一个副本，mid 或 最左侧
            if (nums[mid] == nums[right]) {
                right--;
            //在最小值的左边
            } else if (nums[mid] > nums[right]) {
                left = mid;
            //在最小值的右边
            } else if (nums[mid] < nums[right]) {
                right = mid;
            }
        }

        if (nums[left] < nums[right]) {
            return nums[left];
        }
        return nums[right];
    }
}

33. 搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

使用模板三：

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1; //左右都为闭区间

        while (left + 1 < right) {
            int mid = left + (right - left) / 2;

            //可利用mid跟left 或 right比较从而确定 left 和 mid 或 mid 与 right那个区间是有序的
            //left 和 mid间有序
            if (nums[left] < nums[mid]) {
                if (target >= nums[left] && target <= nums[mid]) {
                    right = mid;
                } else {
                    left = mid;
                }
             //mid 和 right间有序
            } else if (nums[mid] < nums[right]) {
                if (target >= nums[mid] && target <= nums[right]) {
                    left = mid;
                } else {
                    right = mid;
                }
            }
        }

        if (nums[left] == target) {
            return left;
        }

        if (nums[right] == target) {
            return right;
        }

        return -1;
    }
}

81. 搜索旋转排序数组 II

已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。

给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。

使用模板三：

class Solution {
    public boolean search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1; //左右都为闭区间

        while (left + 1 < right) {
            int mid = left + (right - left) / 2;

            //可利用mid跟left 或 right比较从而确定 left 和 mid 或 mid 与 right那个区间是有序的
            if (nums[left] < nums[mid]) {
                if (target >= nums[left] && target <= nums[mid]) {
                    right = mid;
                } else {
                    left = mid;
                }
            } else if (nums[mid] < nums[right]) {
                if (target >= nums[mid] && target <= nums[right]) {
                    left = mid;
                } else {
                    right = mid;
                }
            } else if (nums[left] == nums[mid]) {	//与上例不同点
                left++;
            } else if (nums[right] == nums[mid]) {  //与上例不同点
                right--;
            }
        }

        if (nums[left] == target || nums[right] == target) {
            return true;
        }

        return false;
    }
}