(精华)2020年8月28日 数据结构与算法解析(二分查找)

2020年8月28日 19点热度 0条评论 来源: 愚公搬代码

二分查找也称折半查找,它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。 首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。

示例

public class Program { 

    public static void Main(string[] args) { 
        int[] array = {  8, 11, 21, 28, 32, 43, 48, 56, 69, 72, 80, 94 };

        Console.WriteLine(BinarySearch(array, 80));
        Console.WriteLine(BinarySearch(array, 66, 0, array.Length - 1));

        Console.ReadKey();
    }

    private static int BinarySearch(int[] array, int key) { 
        //直接求解
        var min = 0;
        var max = array.Length - 1;
        var mid = 0;
        while (min <= max) { 
            mid = (min + max) >> 1;
            if (array[mid] > key) { 
                max = mid - 1;
            }
            else if (array[mid] < key) { 
                min = mid + 1;
            }
            else if (array[mid] == key) { 
                return mid;
            } 
        }
        return -1;
    }

    private static int BinarySearch(int[] array, int key, int low, int high) { 
        //递归法
        if (low > high) return -1;
        var mid = (low + high) >> 1;
        if (array[mid] > key)
            return BinarySearch(array, key, low, mid - 1);
        else if (array[mid] < key)
            return BinarySearch(array, key, mid + 1, high);
        else
            return mid;
    }

}

请注意以上递归实现为尾递归:尽量使用尾递归

在最坏的情况下,二分查找需要在最后一次才能查找到目标关键字,假设原问题规模为n,每次折半原问题,设在第k次时问题规模变为1,那么令 2^k=1 ,因为指数和对数互为逆运算,解得 k=log_{2}n ,即二分查找在最坏的情况下的时间复杂度为: O(logn) 。

    原文作者:愚公搬代码
    原文地址: https://blog.csdn.net/aa2528877987/article/details/108276491
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。