Java实现二分查找算法，采用递归和顺序实现方式

分手后的思念是犯贱 2022-01-26 15:31 147阅读 0赞

(一)  实现原理：二分査找就是折半查找，其基本思想是：是在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组 为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。折半搜索每次把搜索区域减少一半，时间复杂度为Ο(logn) 。

（二）实现方式:我采用递归和顺序的方式实现，接下来直接上代码：  
      
    //二分查找递归实现  
    public static int binarySearch(int\[\] arr,int low,int high,int key ) \{  
        int mid = (low + high)/2;  
        if(arr\[mid\] == key) \{  
            index = mid;  
            return mid;  
        \}  
        if(low>high) \{  
            return -1;  
        \}else if(key > arr\[mid\]) \{  
            return binarySearch(arr,mid+1,high,key);  
        \}else if(key < arr\[mid\]) \{  
            return binarySearch(arr,low,mid-1,key);  
        \}  
        return -1;  
              
    \}  
      
    //二分顺序查找实现  
    public static int binarySearch(int\[\] arr,int key ) \{  
        int high = arr.length;  
        int low  = 0;  
        while(low <= high) \{  
            int mid = (low + high)/2;  
            if(key == arr\[mid\]) \{  
                return mid;  
            \}else if(key > arr\[mid\])\{  
                low  = mid + 1;  
            \}else if(key < arr\[mid\])\{  
                high = mid - 1;  
            \}  
        \}  
        return -1;  
    \}

(三)测试

public static void main(String\[\] args) \{  
        int\[\] array = \{1,2,3,4,5,6,7,8,9,10\};  
        System.out.println("递归:所查询值的下标值为："+binarySearch(array,0,array.length-1,7));  
        System.out.println("顺序:所查询值的下标值为："+binarySearch(array,6));  
    \}

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MzI3OTgxMTM_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MzI3OTgxMTM_size_16_color_FFFFFF_t_70]: /images/20220126/2cff065791c44a5f9a94d7e7858315c2.png