折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如 果x<a[n/2]，则我们只要在a的左半部继续搜索x（这里假设数组元素呈升序排列）。如果x>a[n/2]，则我们只要在a的右 半部继续搜索x。

二分查找有个缺点就是元数据必须是有序的，因此二分查找之前必须对对数组排序，可以根据需要选择适当的排序算法这里选择的快速排序算法。

• 首先设定三个变量，lownum，midnum，hignum 假定有十个元素则lownum = 0，hignum=9，midnum=(lownum+highnum)/2.key为查找数据。
• 如果a[midnum] = key，表示查找到数据，返回midnum
• 如果key<a[midnum]则midnum = midnum-1，递归查找a[0] ~ a[midnum-1]
• 如果key>a[midnum]则midnum = midnum+1,递归查找a[midnum+1] ~a[highnum].

 

 

 

下面看一下java的代码实现

package neuq.chao;import java.util.Scanner;class QuickSort{    static void quickSort(int []a,int left,int right){        int ltemp,rtemp,base;        ltemp = left;        rtemp = right;        int t;        base  = a[(right+left)/2];                             //选取中间元素作为边界        while(ltemp
     
      base){                --rtemp;                                //rtemp向左移            }            if(ltemp<=rtemp){               t = a[ltemp];               a[ltemp] = a[rtemp];               a[rtemp] = t;               ++ltemp;               --rtemp;            }        }        if(ltemp==rtemp){            ltemp++;        }        if(left
      
       a[midnum]){            i = binarySearch(a,midnum+1,hignum,key);        }        return i;    } public static void main(String args[]){     int shuzu[] = new int[SIZE];     int h,j,i,n;     for(h=0;h