二分查找（折半查找）

一、概念

二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；

其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。

二、执行过程

折半查找的基本思想为：

（1）在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键码相等，则查找成功；

（2）若给定值小于中间记录的关键码，则在中间记录的左半区继续查找；

（3）若给定值大于中间记录的关键码，则在中间记录的右半区继续查找；

（4）不断重复上述过程，直到查找成功或失败。

三、伪代码描述

（1）设置初始查找区间：low=0，high=n-1；

（2）测试查找区间[low,hig]是否存在，若不存在，则查找失败，否则：（即 low <= high）

（3）取中间位置mid = (low+high)/2，比较k与r[mid]，有以下三种情况：

(3.1) 若k<r[mid]，则high = mid-1;查找在左半区进行，转第二步；

(3.2) 若k>r[mid]，则low = mid+1;查找在右半区进行，转第二步；

(3.2) 若k=r[mid]，则查找成功，返回记录位置mid;

四、非递归算法

 1 public class BinSearch1 {
 2     public boolean BinSe(int r[],int target){
 3        int low = 0, high = r.length-1;
 4        int mid;
 5        while(low <= high){
 6            mid = (low + high) / 2;
 7            if(target == r[mid])
 8                return true;
 9            else if(target < r[mid])
10                high = mid-1;
11            else if(target > r[mid])
12                low = mid+1;
13        }
14        return false;
15     }
16     public static void main(String[] args) {
17         int r[] = {1,2,3,4,5,6,7,8,9,10};
18         System.out.println(new BinSearch1().BinSe(r,1));
19     }
20 }

五、递归算法

 1 public boolean BinSe2(int r[],int target,int low,int high){
 2         if(low > high)
 3             return false;
 4         else{
 5             int mid = (low+high)/2;
 6             if(target < r[mid])
 7                 return BinSe2(r,target,low,mid-1);
 8             else if(target > r[mid])
 9                 return BinSe2(r,target,mid+1,high);
10             else 
11                 return true;
12         }
13     }