前言
小张是一名大三的大学生, 最近面试了腾讯, 字节跳动等公司, 面试结果不佳. 发现自己的数据结构和算法知识还不够扎实吧, 还需要认真的复习一遍. 因此在这里记录一下自己的学习过程. 算是自己的学习笔记吧, 也希望这些文字能够给读者们一些帮助吧.
正文
什么是二分查找?
二分查找是用于有序数组的查找算法, 时间复杂度为 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=[1,2,3,6,8,9,12], target=2 时, 二分查找的搜索过程为
二分查找 Found.PNG
同样的 nums,target=13 时, 二分查找的搜索过程为
二分查找 NotFound.PNG
可见
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 值插入到数组中的该索引值的位置时, 保持该数组仍然有序.
小结
今天的学习就到这里啦, 第一次写简书, 如果对你的学习有帮助的话, 可以支持一下我呀.
来源: http://www.jianshu.com/p/9187cfdfb9f5