Leetcode 二分查找题小结 Java

二分查找主要用于在范围内搜索指定值 较循环遍历速度快，但还是循环遍历实现简单

Leetcode33 搜索旋转排序数组

思路： 　经典二分查找，首先通过二分查找到旋转中值，然后根据左右值判断在哪半边数组，在进行搜索。

代码：

class Solution { public int search(int[] nums, int target) { int len = nums.length; if(len==0) return -1; if(nums[0]<=nums[len-1]) { for(int i=0;i<len;i++){ if(nums[i]==target){ return i; } } return -1; } int l = 0; int r = len-1; while(l<r){ int mid = (l+r)/2; if(nums[mid]>=nums[r]){ l = mid+1; }else{ r = mid; } } int mid = l; if(target>=nums[0]){ for(int i=0;i<mid;i++){ if(target == nums[i]){ return i; } } return -1; } if(target<=nums[len-1]){ for(int i=mid;i<len;i++){ if(target == nums[i]){ return i; } } } return -1; } }

Leetcode162　寻找峰值

思路： 　也很经典。 　提供了递归的二分查找思路

代码

class Solution { public int findPeakElement(int[] nums) { return search(nums,0,nums.length-1); } public int search(int[] nums,int l ,int r){ if(l==r){ return l; } int mid = (l+r)/2; if(nums[mid]>nums[mid+1]){ return search(nums,l,mid); } return search(nums,mid+1,r); } }

Leetcode378 有序矩阵中第 K 小的元素

示例：

matrix = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ], k = 8,

返回 13。

思路： 　将矩阵最小值设为左值，矩阵最大值设为右值，开始二分查找。 　计算矩阵中小于中值的数 　小于ｋ则想右搜索，大于ｋ则向左搜索

代码：

class Solution { public int kthSmallest(int[][] matrix, int k) { int n = matrix.length; int l = matrix[0][0], r = matrix[n - 1][n - 1]; int mid, cnt = 0, tmp; while (l < r) { mid = (r - l) / 2 + l; cnt = count_less(matrix, mid); if (cnt < k) l = mid + 1; else r = mid; } return l; } //找到矩阵中 <= val的元素个数 public int count_less(int[][] matrix, int val) { int n = matrix.length; int i, j; int res = 0; i = n - 1; j = 0; //从matrix的左下角开始找，一列一列地找小于val的元素个数，然后将其相加 while (i >= 0 && j < n) { if (matrix[i][j] <= val) { res += i + 1; j++; } else i--; } return res; } }