小张的算法复习日记——二分查找

作者 : 开心源码 本文共1958个字,预计阅读时间需要5分钟 发布时间: 2022-05-12 共136人阅读

前言

??小张是一名大三的大学生,最近面试了腾讯、字节跳动等公司,面试结果不佳。发现自己的数据结构和算法知识还不够扎实吧,还需要认真的复习一遍。因而在这里记录一下自己的学习过程。算是自己的学习笔记吧,也希望这些文字能够给读者们少量帮助吧。


正文

什么是二分查找?

??二分查找是用于有序数组的查找算法,时间复杂度为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值插入到数组中的该索引值的位置时,保持该数组依然有序。


小结

今天的学习就到这里啦,第一次写简书,假如对你的学习有帮助的话,可以支持一下我呀。

说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 小张的算法复习日记——二分查找

发表回复