查找

1. 折半查找（顺序表，数据有序排列）

在有序表中，把待查找数据值与查找范围的中间元素值进行比较，会有三种情况出现：

1） 待查找数据值与中间元素值正好相等，则放回中间元素值的索引。

2） 待查找数据值比中间元素值小，则以整个查找范围的前半部分作为新的查找范围，执行1），直到找到相等的值。

3） 待查找数据值比中间元素值大，则以整个查找范围的后半部分作为新的查找范围，执行1），直到找到相等的值

4） 如果最后找不到相等的值，则返回错误提示信息。

int BiSearch(int data[], int x, int beg, int last) {

       if (beg > last) return -1;

       int mid = data.length / 2;

       while (beg <= last) {
           if (data[mid] == x) {
               return mid;
           }
           if (data[mid] > x) {
               beg = mid + 1;
           }
           if (data[mid] < x) {
               last = beg + 1;
           }
       }
       return -1;
   }

int biSearch(int data[], int x) {

        if (data.length <= 0) return -1;

        int first = 0;
        int last = data.length - 1;
        int mid = (first + last) / 2;

        while (mid <= data.length - 1) {
            if (data[mid] == x) return mid;
            if (data[mid] > x) last = mid - 1;
            if (data[mid] < x) first = mid;
        }
        return -1;
    }