查找算法之折半查找

折半查找又称为二分查找，其要求查找的序列是一个有序序列（递增或递减），其查找过程：折半查找就是每查找一次，就将序列减少一半，不断缩小查找范围，直到查找成功（也可能查找失败）。
例如：
一个有序序列array为（2，4，5，7，9，15，18，20，23，25，28），要查找的元素key为7；
我们定义三个指针left、mid、right分别指向序列的下界、序列的中间位置、序列的上界，即left=0，right=array.length-1=10，mid=(left+right)/2=5；array[left]=2，array[right]=28，array[mid]=15。
1）首先我们将array[mid]与key进行比较，mid>key,那我们下一次只需要在序列的左半边进行查找，left=0，right=mid-1=4，mid=(left+right)/2=2；array[left]=2，array[right]=9，array[mid]=5。
2）继续将array[mid]与key进行比较，key>array[mid]，left=mid+1=3，right=4，mid=(left+right)/2=3；array[left]=7，array[right]=9，array[mid]=7。
3）再将array[mid]与key进行比较,array[mid]=key,查找成功。

算法实现：

public class binary_Search {
    public int search(int[] array,int searchKey){
        int left = 0, mid , right = array.length - 1;
        while(left <= right){
            mid = (left + right)/2;
            if(mid == searchKey){
                return mid;   //返回下标
            }
            if(mid < searchKey){
                right = mid - 1;
            }
            if(mid > searchKey){
                left = mid + 1;
            }
        }
        return -1;  //查找失败
    }

    public static void main(String[] args){
        search_Seq ss = new search_Seq();
        int[] array = {2,4,5,7,9,15,18,20,23,25,28};
        int searchKey = 7;
        int ans = ss.search_Seq(array,searchKey);
        System.out.println(searchKey+"是数组的第"+(ans+1)+"位元素");
    }
}

运行结果：

折半查找.png