今天读“谷歌三大论文”看到了“二分查找”这个词,突然一点印象都没有了,记性是被狗吃去了么,最主要的是平时用的少,又没怎么去看他,快点打开书,又看了一遍,再敲了一遍,写点东西,算是再次复习一下。
所谓“二分查找”从字面就可以知道他的意思,一个是“分”一个就是“找”,“分”就是指把“分数据”“找”也就是找数据,唉,又废话了。
具体一个例子,我们要在数组中找一个数据,我们先找到中间的值,然后把要找的数据和中间值进行比较,如过比中间值大,我们就知道要在中间和最末尾之间去找了,反之在头和中间里面找。这样就去掉了一半的数据,再这样一直下去,一直分,一直找。。。当头下标比尾下标还要大的时候,也就不能再分了,如果还没找到,就说明数据不在里面。
一直分,一直找,动作都是一样的,这里我们的“递归”就要出场了,递归也就是自己调用自己。正好符合。“二分查找”就应用到了递归的思想。还要注意的是,能进行“二分查找”对数据是要有要求的。要求就是他们要有序,想想也知道,不然根本就查不到。因此我们在插入数据的时候就要将数据排好序。也就是下面的的insertSorted();方法
下面上代码,注释应该有那么清楚吧:
package 二分查找法; public class BinarySearch { private long[] arr; private int nElem; /* * 构造函数初始化数组和元素个数 */ public BinarySearch(int max) { arr = new long[max]; nElem = 0; } /* * 得到数组中的元素个数 */ public int getSize() { return nElem; } /* * 找到相应的元素的方法 */ public long find(long keySearch) { return binarySearch( keySearch,0,nElem-1); } /* * 二分查找的方法 */ private long binarySearch(long keySearch, int head, int end ) { int mid = (head+end)/2; //找到中间的位置 if(arr[mid]==keySearch) { //要找的数据在数组的中间位置 return mid; //返回下标 } else if(head > end) { //头到尾后面去了,说明没找到 return nElem; } else{ //递归调用 if(keySearch < arr[mid]) { //要查找的值比中间值小 return binarySearch(keySearch, head, mid-1); //说明要找的在head--mid-1之间 } else return binarySearch(keySearch, mid+1, end); //要找的数据比中间值要大,数据在mid+1--end之间 } } /* * 在数组中插入一个元素,由于二分查找法针对的是已经排好序的数据, * 所以在构造数组的时候就要使数组中的元素是有序的。 */ public void insertSorted(long value) { int j; for(j = 0; j < nElem; j++) { if(arr[j]>value) //如果要插入的值在中间,跳出循环,转到下一步 break; } for(int k = nElem; k > j;k--) { //将数据往后面移动一个位置 arr[k] = arr[k-1]; } arr[j] = value; //将新的数据放在正确的位置 nElem ++; //元素数量加1 } /* * 打印出数组中的每一个元素 */ public void display() { for(int i = 0; i < nElem; i++) { System.out.print("arr["+i+"]="+arr[i]+" "); } } public static void main(String[] args) { BinarySearch bs = new BinarySearch(20); bs.insertSorted(23); bs.insertSorted(5); bs.insertSorted(2); bs.insertSorted(13); bs.insertSorted(230); bs.insertSorted(30); bs.insertSorted(123); bs.insertSorted(53); bs.insertSorted(32); bs.insertSorted(163); bs.insertSorted(2930); bs.insertSorted(350); System.out.println("打印出数组中的数据:"); bs.display(); System.out.println(); System.out.println("元素的个数为:"+bs.getSize()); int keysearch = 163; long value = bs.find(keysearch); System.out.println("要查找的数为:"+keysearch+" 位置为:"+value); } }
打印结果:
打印出数组中的数据: arr[0]=2 arr[1]=5 arr[2]=13 arr[3]=23 arr[4]=30 arr[5]=32 arr[6]=53 arr[7]=123 arr[8]=163 arr[9]=230 arr[10]=350 arr[11]=2930 元素的个数为:12 要查找的数为:163 位置为:8
相关推荐
二分查找算法,二分查找算法课件,二分查找算法PPT
二分查找算法
Java二分查找递归算法
二分查找是一种高效的搜索算法,特别适用于有序数组。在这个教程中,我们将深入研究二分查找算法的工作原理,并提供一个Java示例来演示如何实现它。无论您是初学者还是有经验的Java开发者,通过学习这个算法,您将...
算法分析与设计-实验二 二分查找实验报告
C 语言中效率最高的查找方式,非常实用。...函数功能: 二分查找 入口参数: 待查找有序表的首地址 int *a 待查找的数据 int num 出口参数: 查找成功返回数据在有序表中的位置0 ~ n-1,不成功返回 -1
算法导论:二分查找算法。比较简单的算法,ACM QQ群里看到的,通俗易懂。
本代码是利用java语言实现基本数据查询功能,实现算法为二分查找法
//文件名:exp9-2.cpp #include #define MAXL 100 //定义表中最多记录个数 typedef int KeyType; typedef char InfoType[10]; typedef struct { KeyType key;
查找算法:二分查找、顺序查找的实现 参见博客:http://blog.csdn.net/xiaowei_cqu/article/details/7748260
二分查找基于分治算法的实现
二分查找算法是运用分治的典型例子:给定已按升序排好序的n个元素a[0:n-1],现要在这n个元素中找出一特定元素x。所以容易设计出二分搜索算法:在 a[0] [1] [n-1] 中搜索 x, 找到x时返回其在数组中的位置,否则返回-...
二分查找算法是查找算法中的一种效率比较高的查找算法,对于一段数组或者字符串的查找,效率可以更高。
java二分查找算法,用于普通的代码算法。。,。。
Java 二分查找算法的示例代码。 欢迎访问个人博客。 http://blog.csdn.net/evanwang1987