折半查找 订阅
二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。 [1] 展开全文
二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。 [1]
信息
外文名
Binary Search
提出时间
1946
别    称
折半查找
提出者
John Mauchly
应用学科
计算机
中文名
二分查找
适用领域范围
编程语言
缺    点
待查表为有序表
优    点
查找速度快
时间复杂度
O(log2n) [1]
二分查找查找过程
首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。
收起全文
精华内容
下载资源
问答
  • 折半查找

    2017-12-19 22:46:12
    折半查找

    折半查找:

    public static int binarySearch(int[] arr, int key) {
        int low = 0;
        int high = arr.length - 1;
    
        while (low <= high) {
            int mid = (low + high) / 2;
            if (arr[mid] == key) {
                return mid;
            } else if (arr[mid] > key) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }
    展开全文
  • 算法 - 折半查找(C#)

    万次阅读 多人点赞 2019-03-14 20:09:56
    分享一个大牛的人工智能教程。零基础!通俗易懂!风趣幽默!... * [折半查找的前提]: * 1、待查找序列必须采用顺序存储结构。 * 2、待查找序列必须是按关键字大小有序排列。 * * 时间复杂度:O(lo...

    分享一个大牛的人工智能教程。零基础!通俗易懂!风趣幽默!希望你也加入到人工智能的队伍中来!请点击http://www.captainbed.net 

    /*
     * Recursive Binary Search - by Chimomo
     *
     * [折半查找的前提]:
     * 1、待查找序列必须采用顺序存储结构。
     * 2、待查找序列必须是按关键字大小有序排列。
     *
     * 时间复杂度:O(log2n)
     */
    
    namespace RecursiveBinarySearch
    {
        using System;
    
        /// <summary>
        /// The program.
        /// </summary>
        internal class Program
        {
            /// <summary>
            /// Entry point into console application.
            /// </summary>
            public static void Main()
            {
                int[] a = {1, 2, 3, 4, 5, 6, 7, 8, 9};
                Console.WriteLine(BinarySearch(a, 6, 0, 9));
            }
    
            /// <summary>
            /// 在下界为low,上界为high的有序数组a中折半查找数据元素x(递归查找)。
            /// </summary>
            /// <param name="arr">
            /// 待查找数组。
            /// </param>
            /// <param name="x">
            /// 目标元素。
            /// </param>
            /// <param name="low">
            /// 数组元素下标的下界。
            /// </param>
            /// <param name="high">
            /// 数组元素下标的上界。
            /// </param>
            /// <returns>
            /// 若查找到目标元素则返回该目标元素在数组中的下标;否则返回-1。
            /// </returns>
            private static int BinarySearch(int[] arr, int x, int low, int high)
            {
                if (low > high)
                {
                    return -1;
                }
    
                int mid = (low + high) / 2;
                if (x == arr[mid])
                {
                    return mid;
                }
    
                return x < arr[mid] ? BinarySearch(arr, x, low, mid - 1) : BinarySearch(arr, x, mid + 1, high);
            }
        }
    }
    
    // Output:
    /*
    5
    
    */
    /*
     * Non-Recursive Binary Search - by Chimomo
     *
     * [折半查找的前提]:
     * 1、待查找序列必须采用顺序存储结构。
     * 2、待查找序列必须是按关键字大小有序排列。
     *
     * 时间复杂度:O(log2n)
     */
    
    namespace NonRecursiveBinarySearch
    {
        using System;
    
        /// <summary>
        /// The program.
        /// </summary>
        internal class Program
        {
            /// <summary>
            /// Entry point into console application.
            /// </summary>
            public static void Main()
            {
                int[] a = {1, 2, 3, 4, 5, 6, 7, 8, 9};
                Console.WriteLine(BinarySearch(a, 6, 9));
            }
    
            /// <summary>
            /// 在长度为n的有序数组arr中查找值为x的元素(非递归查找)。
            /// </summary>
            /// <param name="arr">
            /// 待查找数组。
            /// </param>
            /// <param name="x">
            /// 目标元素。
            /// </param>
            /// <param name="n">
            /// 数组长度。
            /// </param>
            /// <returns>
            /// 若查找到目标元素则返回该目标元素在数组中的下标;否则返回-1。
            /// </returns>
            private static int BinarySearch(int[] arr, int x, int n)
            {
                int low = 0;
                int high = n - 1;
                while (low <= high)
                {
                    int mid = (low + high) / 2;
                    if (arr[mid] == x)
                    {
                        return mid;
                    }
    
                    if (arr[mid] < x)
                    {
                        low = mid + 1;
                    }
                    else
                    {
                        high = mid - 1;
                    }
                }
    
                return -1;
            }
        }
    }
    
    // Output:
    /*
    5
    
    */

     

    展开全文
  • 折半查找定义 折半查找算法实现及查找过程 折半查找判定树 查找成功 查找失败 总结 补充 链接 查找成功 查找失败 算法思路 算法实现 折半查找判定树 折半查找ASL 折半查找性能 总结 ...

    折半查找定义

    在这里插入图片描述

    折半查找算法实现及查找过程

    public int Binary_Search(int[] a,int n,int key){
    		int low=1,high=n,mid;
    		while(low<=high){
    			mid=(int)((low+high)/2);
    			if(key<a[mid])
    				high=mid-1;
    			else if(key>a[mid])
    				low=mid+1;
    			else return mid;
    		}
    		return 0;
    }
    

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    折半查找判定树

    查找成功
    在这里插入图片描述
    查找失败
    在这里插入图片描述

    总结

    在这里插入图片描述
    在这里插入图片描述

    补充

    链接
    查找成功
    在这里插入图片描述
    查找失败
    在这里插入图片描述
    在这里插入图片描述
    算法思路
    在这里插入图片描述
    算法实现
    在这里插入图片描述
    在这里插入图片描述
    折半查找判定树
    在这里插入图片描述
    折半查找ASL
    在这里插入图片描述
    在这里插入图片描述
    折半查找性能
    在这里插入图片描述
    总结
    在这里插入图片描述
    在这里插入图片描述

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 10,415
精华内容 4,166
关键字:

折半查找