前言
小张是一名大三的大学生，最近面试了腾讯、字节跳动等公司，面试结果不佳。发现自己的数据结构和算法知识还不够扎实吧，还需要认真的复习一遍。因此在这里记录一下自己的学习过程。算是自己的学习笔记吧，也希望这些文字能够给读者们一些帮助吧。
正文
什么是二分查找？
二分查找是用于有序数组的查找算法，时间复杂度为log(N)
二分查找其实源于我们小时候玩的“猜数字”的游戏。例如，小明同学在心里想一个范围在1～1000之间的整数，小美同学说出自己猜的数字后，小明同学会告诉小美是大了，小了还是正好猜中了。小明每一次的提示，其实就是把数字的范围给缩小了。二分查找的道理也是相同的，它充分利用了数组有序的性质，每一次查找都将数字范围缩小了一半。这比从1～1000按顺序去猜数字效率高很多。
二分查找的代码实现
public static int binarySearch(int[] nums, int target) {
if(nums == null || nums.length == 0)
return -1;
int low = 0;
int high = nums.length;
while(low < high) {
int mid = low + (high - low) / 2;
if(nums[mid] == target)
return mid;
else if(nums[mid] > target)
high = mid;
else
low = mid + 1;
}
return low;
}
下界:0 上界:nums.length，它表示的查找范围为[0,nums.length) 左开右闭，因此当low == high时查找就结束了,[low,high)中就不再包含任何数字了。
举个例子来说：
同样的nums，target=13时，二分查找的搜索过程为
可见
1.当找到target时，二分查找能够返回target的索引。
2.当找不到target时，二分查找返回这样一个索引值，当把target值插入到数组中的该索引值的位置时，保持该数组仍然有序。
二分查找基础版本的反思
二分查找的基础版本没有问题，可是当我们查找的target在数组中有多个时，二分查找会返回什么数值呢？是第一个，还是中间的，还是最后一个？仔细思考以后可以得出都不是。那么我们如何写出稳定的算法来找到第一个target和最后一个target呢？
找到第一个target的二分搜索
public int binarySearch_bottom(int[] nums, int target) {
if(nums == null || nums.length == 0)
return -1;
int low = 0;
int high = nums.length;
int mid = 0;
while(low < high){
mid = (low + high) / 2;
if(target <= nums[mid])
high = mid;
else
low = mid + 1;
}
return low;
}
1.当nums[mid] == target时：答案可能是mid或者在mid的左边，因此high = mid
2.当nums[mid] > target时：答案可能在mid的左边，因此high = mid
3.当nums[mid] < target时：答案只可能在mid的右边，因此low = mid + 1
因此将这些条件合并起来，就得到了上述的代码。
返回值的分析：
1.当找到target时，二分查找能够返回最左边的target的索引。
2.当找不到target时，二分查找返回这样一个索引值，当把target值插入到数组中的该索引值的位置时，保持该数组仍然有序。
同理我们可以得到找到最后一个target的二分搜索
public static int binarySearch_upper(int[] nums, int target) {
if(nums == null || nums.length == 0)
return -1;
int low = 0;
int high = nums.length;
int mid = 0;
while(low < high){
mid = (low + high) / 2;
if(target >= nums[mid])
low = mid + 1;
else
high = mid;
}
return low;
}
和上一个算法的原理是一样的，但是求target上界的算法要特别注意一下它的返回值。
返回值的分析：
1.当找到target时，二分查找能够返回最右边的target的索引加上一。
2.当找不到target时，二分查找返回这样一个索引值，当把target值插入到数组中的该索引值的位置时，保持该数组仍然有序。
小结
今天的学习就到这里啦，第一次写简书，如果对你的学习有帮助的话，可以支持一下我呀。
