[查找算法]--二分查找的Java实现

骑猪看日落 2022-07-12 02:58 220阅读 0赞

> 二分查找算法思想：又叫折半查找，要求待查找的序列有序。每次取中间位置的值与待查关键字比较，如果中间位置的值比待查关键字大，则在前半部分循环这个查找的过程，如果中间位置的值比待查关键字小，则在后半部分循环这个查找的过程。直到查找到了为止，否则序列中没有待查的关键字。

下面给出两种实现方式：  
1. 非递归实现：

/** * 非递归方式查找 * @param array * @param a * @return 查找到的索引值 */
    public static int binarySearch1(int[] array, int a){
        int lo=0, hi=array.length-1;
    
        int mid;//中间索引
    
        while (lo <= hi){
            mid = (lo+hi)/2;
    
            if(array[mid] == a){
                return mid;
            } else if(array[mid] < a){
                lo = mid+1;
            }else{
                hi = mid-1;
            }
        }
        return -1;
    }

1.  递归实现：

/** * 递归方式查找 * @param array * @param a * @return */
    public static int binarySearch2(int[] array, int a, int lo, int hi){
    
        if(lo <= hi){
            int mid = (lo+hi)/2 ;
    
            if( a == array[mid] ){
                return mid;
            } else if(a > array[mid]){
                return binarySearch2(array, a, mid+1, hi);
            } else {
                return binarySearch2(array, a, lo, mid-1);
            }
        }
        return -1;
    }

本文全部源代码github：  
[https://github.com/leetcode-hust/leetcode/blob/master/louyuting/src/leetcode/Algorithm/BinarySearch.java][https_github.com_leetcode-hust_leetcode_blob_master_louyuting_src_leetcode_Algorithm_BinarySearch.java]

[https_github.com_leetcode-hust_leetcode_blob_master_louyuting_src_leetcode_Algorithm_BinarySearch.java]: https://github.com/leetcode-hust/leetcode/blob/master/louyuting/src/leetcode/Algorithm/BinarySearch.java