浙江省建设职业技术学院网站,好建设网站,公司展示网站制作,建设监理杂志网站算法 - 二分查找 今天继续八股文学习#xff0c;看一下比较常规的几个算法 二分查找是一个基于分治策略的搜索方法#xff0c;简单的理解就是每次都缩小一轮搜索范围#xff0c;从中间search一次#xff0c;直到搜索到结果或者为空为止。
基本思路#xff08;设一个有序的…算法 - 二分查找 今天继续八股文学习看一下比较常规的几个算法 二分查找是一个基于分治策略的搜索方法简单的理解就是每次都缩小一轮搜索范围从中间search一次直到搜索到结果或者为空为止。
基本思路设一个有序的数组为nums需要查询的值是target
设置 i 0j n -1。i就是数组开头的第一个索引值j就是最后一个索引值。如果i j 了证明查询结束了没有找到结果。然后设置一个值为m这个m就是减少的搜索范围应该说成是每次拿数组中间的那个值数组的中间索引m (i j )/ 2 有的时候会有小数所以这个时候需要取整。如果target的值小于数组中间的值也就是索引值是m的值那就意味着这个值在中间值的左边数组中间的靠左的位置所以 j m - 1数组的最大值挪到了中间值靠左的位置然后我们再重复回到第二步继续跑。如果target的值大于数组中间的值意味着这个值在中间值的右边所以 i m 1数组的最小值挪到了中间值靠右的位置然后再重复回到第二步继续跑。当索引值m target的时候就直接return返回查询的结果值。
/*** 二分查找* p* 基于分治策略的的高效搜索方法。* p* 每轮都缩小一般的搜索范围直到搜索到结果或者区间的结果为空的时候停止。*/
public class BinarySearch {// 只能用于有序的数组的排序public static void main(String[] args) {int[] nums new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};int target 11;System.out.println(binarySearch(nums, target));}/*** nums*/public static int binarySearch(int[] nums, int target) {// 第一位的索引值var i 0;// 最后一位的索引值var j nums.length - 1;while (i j) {// 先拿一个中间点并且需要取整因为有时候可能回出现小数点int m i (j - i) / 2;// 如果中间值的小于目标值则往中间值的左边靠if (nums[m] target) {i m 1;} else if (nums[m] target) { // 如果中间值大于目标值则往中间值的右边靠j m - 1;} else {return m;}}// 如果找不到元素返回 -1return -1;}
}优点 在时间和空间方面都有较好的性能。 二分查找的时间效率高不需要额外的空间。
局限性
二分查找仅适用于有顺序的数据如果单独为了跑这个二分查找再进行一次排序就得不偿失了并且二分查找仅适用于在数组上跑因为二分查找需要频繁的移动指针跳跃式访问链表执行跳跃式访问的效率比较低。当数据量小的时候使用线性查找比二分查找的效率要高。下一篇写一下线性查找
