二分查找及其应用总结
1. 二分查找及应用
二分查找是一种常见的搜索算法，思想很简单，麻烦的地方在于边界细节处理。坊间戏言二分查找属于玄学编程，可见细节处理确实让大家比较头疼。网上也有不少二分查找模板，大家可以自行搜索。
为了便于总结和学习二分查找算法，本文总结了一些常见使用场景，粗略分类如下：
查找特定值
查找特定值的左右边界
查找比特定值大的值
查找最小值
查找峰值
本文第六部分也粗略总结了一个模板和注意事项，主要是便于个人理解，欢迎大家指正。
2 查找特定值
2.1 LCD33 查找旋转的排序数组中特定值
public int search(int[] nums, int target) {return binarySearch(nums,0,nums.length-1,target);}int binarySearch(int[] nums, int low, int high, int target) {if (low > high) return -1; //非法区间，尝试了所有的查找区间仍为找到结果int middle = (low + high) / 2;if (nums[middle] == target) return middle; //找到目标if (nums[low] <= nums[middle]) { //若low到middle是有序的if (nums[low] <= target && target < nums[middle])return binarySearch(nums, low, middle - 1, target);elsereturn binarySearch(nums, middle + 1, high, target);} else { //middle到high是有序的if (nums[middle] < target && target <= nums[high])return binarySearch(nums, middle + 1, high, target);elsereturn binarySearch(nums, low, middle - 1, target);}}
2.2 LCD81 查找旋转的排序数组中特定值，有重复元素
public boolean search(int[] nums, int target) {return binarySearch(nums, 0, nums.length - 1, target);}boolean binarySearch(int[] nums, int low, int high, int target) {if (low > high) return false;int middle = (low + high) / 2;if (nums[middle] == target) return true;if (nums[low] < nums[middle]) { //low到middle是有序的if (nums[low] <= target && target < nums[middle])return binarySearch(nums, low, middle - 1, target);elsereturn binarySearch(nums, middle + 1, high, target);} else if(nums[low] > nums[middle] ) { //middle到high是有序的if (nums[middle] < target && target <= nums[high])return binarySearch(nums, middle + 1, high, target);elsereturn binarySearch(nums, low, middle - 1, target);} elsereturn binarySearch(nums, low + 1, high, target); //去重}
2.3 LCD74 查找有序矩阵的目标值，矩阵如下特性：
每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数
public boolean searchMatrix(int[][] matrix, int target) {if(matrix == null || matrix.length == 0 ) return false;int rows = matrix.length;int cols = matrix[0].length;int low = 0, high = rows*cols -1;int mid,midElement;while( low <= high){mid = (low + high)/2;midElement = matrix[mid/cols][mid%cols]; //转换成行列if( midElement == target) return true;else if(midElement > target) high = mid -1;else low = mid +1;}return false;}
2.4 LCD240 查找有序矩阵的目标值，矩阵如下特性：
每行的元素从左到右升序排列
每列的元素从上到下升序排列
public boolean searchMatrix(int[][] matrix, int target) {if( matrix == null || matrix.length == 0 || matrix[0].length == 0)return false;int row = 0, col = matrix[0].length -1; //选择从右上角落开始搜，往下变大，往左变小int mid ;while( row <= matrix.length-1 && col >= 0 ){if( matrix[row][col] == target)return true;else if(matrix[row][col] < target)row ++;elsecol --;}return false;}
3 查找特定值的左右边界
3.1 LCD34 在排序数组中查找元素的第一个和最后一个位置
int findStart(int[] nums, int low, int high, int target) {if (low > high) return -1;int middle = (low + high) / 2;if (nums[middle] == target && (middle == 0 || nums[middle - 1] < nums[middle]))return middle;if (target <= nums[middle])return findStart(nums, low, middle - 1, target);elsereturn findStart(nums, middle + 1, high, target);}int findEnd(int[] nums, int low, int high, int target) {if (low > high) return -1;int middle = (low + high) / 2;if (nums[middle] == target && (middle == nums.length - 1 || nums[middle + 1] > nums[middle]))return middle;if (target >= nums[middle])return findEnd(nums, middle + 1, high, target);elsereturn findEnd(nums, low, middle - 1, target);}
4 查找比特定值大的值
4.1 LCD744 寻找比目标字母大的最小字母
public char nextGreatestLetter(char[] letters, char target) {return nextGreatestLetter(letters,target,0,letters.length -1 );}public char nextGreatestLetter(char[] letters, char target, int low, int high) {if (low > high) return letters[0]; //查找区间都没有找到比target大的字母，则返回letters中的第一个字母int mid = low + (high - low) / 2;if( letters[mid] > target && (mid == 0 || letters[mid-1] <= target))return letters[mid];if( letters[mid] <= target)return nextGreatestLetter(letters,target,mid+1,high);elsereturn nextGreatestLetter(letters,target,low,mid-1);}
5 查找最小值
5.1 LCD153 寻找旋转排序数组中的最小值
public int findMin(int[] nums) {if(nums.length == 1) return nums[0];return findMin(nums,0, nums.length-1);}public int findMin(int[] nums, int l, int h) {if( l > h) return -1; //just for return, unreachableint m = (l + h) / 2;if( m >=1 && nums[m-1] > nums[m]) return nums[m]; // 解空间为[1, nums.length-1]if( m==0 && nums[m] < nums[m+1]) return nums[m]; // 解为0if ( nums[m] >= nums[h])return findMin(nums,m+1,h);elsereturn findMin(nums,l,m-1);}
5.2 LCD154 寻找旋转排序数组中的最小值-ii, 可能存在重复元素
public int findMin(int[] nums) {if(nums.length == 1) return nums[0];return findMin(nums,0, nums.length-1);}public int findMin(int[] nums, int low, int high){if( l > h) return -1; //just for return, unreachableint m = (l + h) / 2;if( m >=1 && nums[m-1] > nums[m]) return nums[m];if( m==0 && nums[m] <= nums[m+1]) return nums[m];if ( nums[m] > nums[h])return findMin(nums,m+1,h);else if( nums[m] < nums[h])return findMin(nums,l,m-1);elsereturn findMin(nums,l,h-1);}
五 查找峰值
5.1 LCD162 寻找峰值
public int findPeakElement(int[] nums) {if( nums.length == 1) return 0;return binarySearch(0, nums.length -1,nums);}public int binarySearch(int l, int h, int[] nums) {if (l > h ) return -1; //just for return, unreachableint m = (l + h)/2;if( m >=1 && nums[m] > nums[m-1] && m+1 <= nums.length -1 && nums[m] > nums[m+1])return m; // 解空间为[1, nums.length-2]if( m == 0 && nums[m] > nums[m+1] || m == nums.length -1 && nums[m] > nums[m-1])return m; // 解空间包含0和nums.length-1if( nums[m] < nums[m + 1])return binarySearch(m+1, h, nums);elsereturn binarySearch(l,m-1,nums);}
六 要点总结
通过前面例子，我们可以总结出二分查找的基本步骤：
public int binarySearch(int l, int h, int[] nums, int target) {if( l > h) .....; // 注意点 1)int m = l + (h - l) / 2 ; // 注意点 2)if(.....) return m; // 注意点 3)if(.....) // 注意点 4)return binarySearch(m+1, h, nums);elsereturn binarySearch(l,m-1,nums);}
1) 越界处理
如果步骤3)中处理逻辑覆盖了所有元素，那这里只用返回-1即可，表示所nums中所有元素都不符合算法目标，实际应用中，可以会返回-1、false、null等。
2) 求取中间值
一般使用 int m = l + (h -l) / 2 代替 ( h+l ) / 2，后者会存在溢出情况。
3) 满足条件则返回解
nums数组中的所有元素都有可能是算法的一个解，需要注意返回结果中是否考虑到了所有元素，不要有遗漏的情况。
4) 收缩查找区间
查找特定值的，一般用nums[mid]和nums[target]的比较结果来决定收缩哪部分查找区间；其他类型，nums[mid]可能需要和nums[low]、或nums[high]、或nums[mid+1]、或nums[mid-1]比较。
5) 去重处理
如果数组中存在重复元素，当nums[low] == nums[mid]时，只用继续查找[low+1,high]即可，如LCD81和LCD154。
七 延申
LCD35题目是如下：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。你可以假设数组中无重复元素。按照第六部分总结得出解法如下：
public int searchInsert(int[] nums, int target) {return searchInsert(nums,target,0, nums.length-1);}public int searchInsert(int[] nums, int target,int l, int h) {if(l > h) return -1; // just for return ,unreachableint mid = l + (h - l) / 2 ;if( nums[mid] == target) return mid; //找到返回索引if( nums[mid] < target && mid + 1 <= nums.length -1 && target < nums[mid+1]) return mid+1; //解空间[1,nums.length-1]if( mid == 0 && target < nums[0]) return mid; //解空间0if( mid == nums.length -1 && target > nums[mid]) return mid +1; //解空间nums.lengthif (nums[mid] > target)return searchInsert(nums,target,l,mid-1);elsereturn searchInsert(nums,target,mid+1,h);}
上面这种写法略显复杂的，好处是考虑了所有的返回情况，比较好理解。其实有个更简洁的写法，如下：
public int searchInsert(int[] nums, int target) {int l = 0, h = nums.length-1;while(l <= h){int mid = l + (h-l)/2;if( nums[mid] == target) return mid;if (nums[mid] > target)h = mid -1;elsel = mid +1;}return l; //l = h +1,l的区间范围是[0,nums.length]}