leetcode刷题思路-----二分查找
基本模板
二分需要纯纯模板，不要再因题制宜的写了，越多越混。直接一个固定的模板，所有的都写一个，对结果再特判。
public class MyBinarySearch {
public static void main(String[] args) {
//对于一个有序数组
int[] nums = new int[]{2,3,4,5,5,5,7};
//查找一个小于最小的数，返回0
System.out.println(search(nums,0));
//对于存在重复的数，返回第一个数的索引位置
System.out.println(search(nums,5));
//对于不存在数组的数，返回第一个比他大的数的索引
System.out.println(search(nums,6));
//正常的返回其索引
System.out.println(search(nums,7));
//对于查找大于数组最大的数，返回nums.length-1
System.out.println(search(nums,8));
}
//二分模板
private static int search(int[] nums,int target){
int left = 0;
int right = nums.length-1;
while(left<right){
int mid = (left+right)/2;
//注意不要越界
if(left<right&&nums[mid]<target){
left = mid+1;
}else{
right = mid;
}
}
//返回索引
return left;
}
}
实战题型
实战基本上没有白给的让你查找，这个思路要自己挖掘。比如题里要求OlogN的复杂度，那基本九成九是要二分了。
1.防止越界（超时）：
x的平方根
搜索二维矩阵
2.模板的稍稍修改：
153. 寻找旋转排序数组中的最小值
154. 寻找旋转排序数组中的最小值 II
总结
二分是对顺序查找的一种时间优化，本着分治的思路解决问题。对于leetcode题目需要多刷才会深刻理解什么时候需要二分。而反过来，对于二分题目最好要死记硬背模板，一个模板再加上特判才能快速解决问题。
