当使用二分查找时就体现出排序的重要性，这种查找比线性查找要快很多，尤其是对较大的数据来说更为显著。
二分查找类似猜数字的游戏，一个朋友让你才她正在想的一个1到100之间的数。当你猜了一个数后，她会告诉你三种情况：你猜的数比她想的大，或小，或猜中了。于是，你从50开始猜，如果她说你猜的数比较小，那么她的数在51-100，否则，在1-49。这样每猜一次，可能的值就会划分为两部分，最后范围会缩小到一个数字，即最后答案。
下面是二分查找法的Java实现：
public int BinarySearch(long searchKey){ int low = 0; int high = n - 1; int mid; while(true){ mid = (low + high) / 2; //初始值 if (a[mid] == searchKey) //找到 return mid; else if (low > high) //寻找完毕，没有找到 return n; else{ if (a[mid] < searchKey) //在上半部分 low = mid + 1; else high = mid - 1; //在下半部分 } } }
现在，运用以上的二分查找法来实现一个包含该方法的有序数组类：
public OrdArray{ private long[] a; private int nElems; public OrdArray(int max){ a = new long[max]; nElems = 0; } public int size(){ return nElems; } public int find(long searchKey){ int lowerBound = 0; int upperBound = nElems -1; int curIn; while (true){ curIn = (lowerBound + upperBound) / 2; if (a[curIn] == searchKey) return curIn; else if (lowerBound > upperBound) return nElems; else { if (a[curIn] < searchKey) lowerBound = curIn + 1; else upperBound = curIn - 1; } } } public void insert(long value){ int j; for (j = 0; j < nElems; j++) //找到要插入的位置 if (a[j] > value) //线性查找，也可以二分查找 break; for (int k = nElems; k > j; k--) //j之后的向右移位 a[k] = a[k - 1]; a[j] = value; //插入 nElems++; } public boolean delete(long value){ int j = find(value); //调用二分查找的方法 if (j == nElems) //没有找到 return false; else { for (int k = j; k < nElems; k++) //向左移位 a[k] = a[k+1]; nElems--; return true; } } public void display(){ for (int j = 0; j < nElems; j++) System.out.println(a[j] + " "); } }
原文：http://www.cnblogs.com/lahwf/p/6380390.html