| 二分查找法 | 您所在的位置：网站首页 › 分类目录检索法 › 二分查找法 |
二分查找法
|
最近整理了一下几个算法，这篇就来说说二分法，适用于小白。 不说废话，先讲讲什么是二分法 二分法，也称为折半查找法，是一种适用于大量数据查找的方法，但是要求数据必须的排好序的，每次以中间的值进行比较，根据比较的结果可以直接舍去一半的值，直至全部找完（可能会找不到）或者找到数据为止。 下面讲讲二分法的查找过程是什么样的，为了直观的讲解，我们以一组样例数据来模拟整个算法 以 1,3,20,24,44,67,71,82,90,110 为例，我们需要用二分法来查找 71 的位置 1.我们建立一个以为数组，存放 {1,3,20,24,44,67,71,82,90,110} 这一组样例数据并且取两个核心下标，分别是头部top和尾部end这两个下标 最后附上代码 public static void binarySearch(){ int[] number = new int[]{1,3,20,24,44,67,71,82,90,110};//样例数据 int key = 20;//需要找的值 int top = 0,end = number.length -1 ,mid;//定义头部，中部，和尾部三个下标 int find = -1;//定义需要找的数的下标，-1说明没找到 while(top //如果找到，直接跳出循环 find = mid; break; }else if(number[mid] > key){//如果当前值比需要找的值大，就将尾部的下标移至mid的前一处 end = mid - 1; }else{//如果当前值比需要找的值小，就将头部的下标移至mid的后一处 top = mid + 1; } } //输出查找的结果 if(find >= 0){ System.out.println(key + "在下标"+find+"的位置"); }else{ System.out.println("没有找到"); } } public static void main(String[] args) { binarySearch(); }新人第一次写，希望大家看完这篇能够理解。 |
2.每次查找的时候都是取top与end中间位置，所以第一次 mid = 4 指向 44 
而 44 比我们需要找的 71 小，所以我们需要将 top 指针移动到 mid + 1 的位置，因为数据是有序的，所以 44 之前的数据可以直接排除 
3.再次取中间值，这次 mid 应该是 7，指向 82 ，而 82 比 71 大，这时候我们需要将 end 位置移动至 mid -1 处，与上面原因同理，比 82 大的都需要排除 
4.继续，这次 mid 应该是 （5 + 6）/ 2 = 5 ，指向 67，67 小于 71，将 top 移动至 mid +1 处 
5.相信应该看出来了，下面是最后一步，mid = （6 + 6）/ 2 ，mid = 6，指向 71 ，正好找到 71 
到此整个二分法的整个查找过程结束了，之所以成为二分法，是因为每次都是排除一半的数据，所以开头讲到为什么需要排序后的数据就是这个原因。【本文地址】