本专栏只专注二分法的解法，若有其它简便解法暂不考虑。
从几乎零基础开始学算法，多多包涵，共同进步！
class Solution {
public boolean isPerfectSquare(int num) {
int l=0,r=num;
while(l<=r){
int m=l+(r-l)/2;
if((long)m*m==num) return true;
if((long)m*m>num){
r = m-1;
}else {
l = m+1;
}
}
return false;
}
}
思路：最基础的二分题，主要是边界会出现问题。
class Solution {
public int mySqrt(int x) {
if(x==0||x==1)return x;
int l = 0,r=x/2+1,ans=-1;
int m=0;
while(l<=r){
m=l+(r-l)/2;
if((long)m*m>x){
r = m-1;
ans = r;
}else{
l = m+1;
}
}
return ans;
}
}
class Solution {
public int findPeakElement(int[] nums) {
int l=0,r=nums.length-1;
while(l<r){
int m=(r+l)/2;
if(nums[m+1]>nums[m]){
// 如果 m + 1 更大， 说明 m 之后肯定还在爬升，m+1 之后有峰
l = m+1;
}else{
// 如果 m 更大， 说明 m 之前有峰
r = m;
}
}
return r;
}
}
思路：此题目数组无序，用上二分法，理解起来有一定难度。但是，只要理解代码中标注的话，就会豁然开朗。
拓展：因为此专栏上次的文章讲了动态规划，便试着用滚动数组的思想写了另外的解法，时间复杂度依然能击败100%，算是学以致用：
class Solution {
public int findPeakElement(int[] nums) {
boolean q=true,p=true;
for(int i=0;i<nums.length-1;i++){
q= p;
p= (nums[i+1]>nums[i]) ;
if(q==true&&p==false) return i;
if(i==(nums.length-2)&&q==true&&p==true){
return i+1;
}
}
return 0;
}
}
**
**
class Solution {
public int kthSmallest(int[][] matrix, int k) {
int row = matrix.length;
int col = matrix[0].length;
int left = matrix[0][0];
int right = matrix[row - 1][col - 1];
while (left < right) {
// 每次循环都保证第K小的数在start~end之间，当start==end，第k小的数就是start
int mid = left+(right - left) / 2;
// 找二维矩阵中<=mid的元素总个数
int count = findNotBiggerThanMid(matrix, mid, row, col);
if (count < k) {
// 第k小的数在右半部分，且不包含mid
left = mid + 1;
} else {
// 第k小的数在左半部分，可能包含mid
right = mid;
}
}
return right;
}
private int findNotBiggerThanMid(int[][] matrix, int mid, int row, int col) {
// 以列为单位找，找到每一列最后一个<=mid的数即知道每一列有多少个数<=mid
int i = row - 1;
int j = 0;
int count = 0;
while (i >= 0 && j < col) {
if (matrix[i][j] <= mid) {
// 第j列有i+1个元素<=mid
count += i + 1;
j++;
} else {
// 第j列目前的数大于mid，需要继续在当前列往上找
i--;
}
}
return count;
}
}
思路：此题目有一定难度，如果看不明白以上代码，建议直接去leetcode看题解。
最简单的解法：想到要排序就好解决，直接暴力。
class Solution {
public int triangleNumber(int[] nums) {
int len = nums.length;
Arrays.sort(nums);
int count=0;
for(int i=0;i<len-1;i++){
for(int j=i+1;j<len;j++){
int l=j+1,r=len-1,k=j;
while(l<=r){
int m=(r+l)/2;
if(nums[m]<nums[i]+nums[j]){
l=m+1;
k=m;
}else r=m-1;
}
count += k-j;
}
}
return count;
}
}
方法二：
class Solution {
public int triangleNumber(int[] nums) {
int len = nums.length;
Arrays.sort(nums);
int count=0;
for(int i=0;i<len-1;i++){
for(int j=i+1;j<len;j++){
int l=j+1,r=len-1,k=j;
while(l<=r){
int m=(r+l)/2;
if(nums[m]<nums[i]+nums[j]){
l=m+1;
k=m;
}else r=m-1;
}
count += k-j;
}
}
return count;
}
}
思路：方法二可以说是方法一的优化，方法一三层循环，方法二可以在第三层循环处做文章–使用二分法，减小时间复杂度