【数据结构与算法之排序与查找】折半查找算法

今天药忘吃喽~ 2024-03-25 16:39 116阅读 0赞

#### 【数据结构与算法之排序与查找】折半查找算法 ####

#### 文章目录 ####

*   *   *  【数据结构与算法之排序与查找】折半查找算法

折半查找算法是利用分治的算法思想设计的静态查找算法。

折半查找算法有严格的使用条件，它只适用于有序排列的关键字序列。

另外折半查找算法需要随机访问序列中的元素，因此只能在顺序结构(顺序表或数组)中进行，不适用于链表存储的数据序列。

折半查找算法采用了分而治之的思想，将问题的规模不断缩小，平均查找长度为  A S L ≈ l o g 2 ( n + 1 ) − 1 ASL ≈ log\_2^\{(n + 1)\} - 1 ASL≈log2(n\+1)−1

因此时间复杂度为  O ( l o g 2 n ) O(log\_2^n) O(log2n)， 而且序列如果越长，那么折半查找的效率优势就越明显。

折半查找算法可以用递归和非递归两种方式实现，本质上没有区别，只是递归方式利用了折半查找算法的特性，代码更加简洁。实际应用中，如果数据量特别大， 还是推荐使用非递归，因为递归算法消耗空间资源较大。

非递归实现Java 描述：

/**
     * 非递归实现二分查找
     * @param array
     * @param k
     * @return
     */
    public static int binarySearch(int[] array, int k) {
        
        int low = 0, high = array.length - 1, mid;
    
        while (low <= high) {
        
            mid = (low + high) / 2;
            if (array[mid] == k) {
        
                return mid;  // 查找成功，返回mid
            }
            if (k > array[mid]) {
        
                low = mid + 1; // 在后半序列中查找
            } else {
        
                high = mid - 1; // 在前半序列中查找
            }
        }
    
        return -1;  // 查找失败，返回-1
    }

递归Java 描述：

/**
     * 递归方式实现二分查找
     *
     * @param array
     * @param low
     * @param high
     * @param k
     * @return
     */
    public static int binarySearch(int[] array, int low, int high, int k) {
        
    
        int mid;
        if (low > high) {
        
            return -1; // low > high，查找失败，返回-1
        } else {
        
            mid = (low + high) / 2;
            if (array[mid] == k) {
        
                return mid;
            }
            if (k > array[mid]) {
        
                // 递归后半序列
                return binarySearch(array, mid + 1, high, k);
            } else {
        
                // 递归前半序列
                return binarySearch(array, low, mid - 1, k);
            }
        }
    }

测试

public static void main(String[] args) {
        
    
        int[] array = {
        2, 3, 5, 8, 9, 11, 13, 17, 21};
    
        int pos = binarySearch(array, 17);
        System.out.println(pos);
    
        pos = binarySearch(array, 0, 8, 8);
        System.out.println(pos);
    }

运行结果

![在这里插入图片描述][864624cf885145d6b67c579a7b72619c.png_pic_center]

[864624cf885145d6b67c579a7b72619c.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/31be0f89ab624d9f8334d100b9b25692.png