二分法查找[折半查找][Java实现]

二分法[折半]查找的基本思想:　　用指定的关键字与查找表中间位置数据元素的关键字比较。如果二者相等，则查找成功；否则以中间元素为界，将查找表分为前、后两部分。如果中间元素关键字大于给定关键字，则在前一子表进行折半查找；否则在后一子表进行折半查找。重复上述过程，直到出现匹配的数据元素，则查找成功。反之，如果直到子表为空时仍未找到，则查找失败。

待查找的元素:

package org.pbdevj.ds.search.binarysearch;/**带排序的元素*/public class Element implements Comparable<Element> {private Object eValue;public void seteValue(Object eValue) {this.eValue = eValue;}public Object geteValue() {return eValue;}public Element() {// TODO Auto-generated constructor stub}public Element(Object eValue) {// TODO Auto-generated constructor stubthis.eValue = eValue;}@Overridepublic String toString() {// TODO Auto-generated method stubreturn eValue==null?””:eValue.toString();}@Overridepublic int compareTo(Element o) {// TODO Auto-generated method stubreturn this.toString().compareTo(o.toString());}}

查找回调接口:

package org.pbdevj.ds.search.binarysearch;/**搜索回调接口*/public interface ISearchCallBack {void visit(Element e);}

查找接口：

package org.pbdevj.ds.search.binarysearch;/**查找接口*/public interface ISearch {int search(Element e);int search(Element e,ISearchCallBack searchCallBack);}

二分法查找实现类：

package org.pbdevj.ds.search.binarysearch;/**二分法查找*/public class BinarySearch implements ISearch {private Element[] elements;public BinarySearch(Element[] elements) {// TODO Auto-generated constructor stubthis.elements = elements;}@Overridepublic int search(Element e) {return search(e,null);}@Overridepublic int search(Element e, ISearchCallBack searchCallBack) {if (elements==null || e == null)return -1;int pstart=0;//开始指针int pend = elements.length;//结束指针[指向查找范围的末元素的后一个位置]int middle=0;//中间位置while(pstart<pend){middle = (pstart+pend)/2;if (searchCallBack!=null)searchCallBack.visit(elements[middle]);//分三种情况讨论//中间位置的比较关键字元素和待查找元素相等if (elements[middle].compareTo(e)==0)//相等则找到return middle;//中间位置的比较关键字元素小于待查找元素if(elements[middle].compareTo(e)<0)pstart=middle+1;//中间位置的比较关键字元素大于于待查找元素if(elements[middle].compareTo(e)>0)pend=middle;}return -1;}}

junit4单元测试:

package org.pbdevj.ds.search.binarysearch.utest;import org.junit.*;import org.pbdevj.ds.search.binarysearch.BinarySearch;import org.pbdevj.ds.search.binarysearch.Element;import org.pbdevj.ds.search.binarysearch.ISearch;import org.pbdevj.ds.search.binarysearch.ISearchCallBack;public class BinarySearchTest {private Element[] elements;private ISearch search;private Element searchElement;@Beforepublic void init(){elements = new Element[]{new Element(10),new Element(20),new Element(30),new Element(40),new Element(50),new Element(60),new Element(70),new Element(80)};search = new BinarySearch(elements);searchElement = new Element(10);}@Testpublic void testSeartch(){final Counter counter = new Counter();//查找次数int index = search.search(searchElement,new ISearchCallBack() {@Overridepublic void visit(Element e) {System.out.println(“查找第”+(counter.increment())+”次[“+e+”]”);}});Assert.assertTrue(index!=-1);System.out.println(“the location:”+index);}class Counter{private int count=0;public int increment(){return ++count;}}}

测试控制台输出：

　　　查找第1次[50]　　　查找第2次[30]　　　查找第3次[20]　　　查找第4次[10]　　　the location:0

也有伤心的，既有令人兴奋的，也有令人灰心的，