折半查找，binarySearch

折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用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<rtemp){
            while(a[ltemp]<base){
                ++ltemp;                                   //ltemp向右移
            }
            while(a[rtemp]>base){
                --rtemp;                                //rtemp向左移
            }
            if(ltemp<=rtemp){
               t = a[ltemp];
               a[ltemp] = a[rtemp];
               a[rtemp] = t;
               ++ltemp;
               --rtemp;
            }
        }
        if(ltemp==rtemp){
            ltemp++;
        }
        if(left<rtemp){
            quickSort(a,left,ltemp-1);
        }
        if(ltemp<right){
            quickSort(a,rtemp+1,right);
        }
    }
}

public class BinarySearch {                        //折半查找
    static final int SIZE = 10;
    static Scanner input = new Scanner(System.in);
    static int binarySearch(int []a,int left,int right,int key){
        int lownum,midnum,hignum;
        lownum = left;
        midnum = (left+right);
        hignum = right;
        int i =-1;
        if(key==a[midnum]){
            i =  midnum;
        }
        if(key<a[midnum]){
           i =    binarySearch(a,lownum,midnum-1,key);
        }
        if(key>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<SIZE;h++){
        shuzu[h] = (int)(100+Math.random()*(100+1));
     }
    // QuickSort qs = new QuickSort();
     QuickSort.quickSort(shuzu,0,SIZE-1);
     System.out.print("数组的数据为: 
");
     for(i=0;i<SIZE-1;i++){
         System.out.print(shuzu[i]+" ");
     }
     System.out.print("
");
     System.out.print("请输入查找的数据： 
");
     n = input.nextInt();
     j = binarySearch(shuzu,0,SIZE-1,n);
     if(j<0){
         System.out.print("未查找到数据");
     }
     else{
         System.out.print(n+"是数组中第"+j+"个数");
     }
 } 
}