算法之二分查找

排序算法

二分查找

用于有序元素列表的查找
性能：

• Python实现：

def binary_search(list, item):
   '''二分查找 
    list:数组列表
    item：要查询的值    
    '''
    num=0
    low_index = 0 
    high_index = len(list)-1
    while low_index <= high_index: 
        num+=1
        mid = (low_index + high_index)//2
        guess = list[mid]
        if guess == item: 
            return "的索引为"+str(mid)+",查询次数为"+str(num)
        if guess > item: 
            high_index = mid - 1
        else: 
            low_index = mid + 1

    return "值在数组中不存在,查询次数为"+str(num) 

• C#实现

        /// <summary>
        /// 二分查找每个数
        /// </summary>
        /// <returns></returns>
        public static string Binary_search(int[] list, int item)
        {           
            var num = 0;
            var low_index = 0;
            var high_index = list.Length - 1;
            while (low_index <= high_index) 
            {
                num += 1;
                var mid = (low_index + high_index)/2;
                var guess = list[mid];
                if (guess == item)
                {
                    return $"的索引为{mid}查询次数为{num}";
                }
                else if (guess > item)
                {
                    high_index = mid - 1;
                }
                else
                {
                    low_index = mid + 1;
                }
            }
            return $"值在数组中不存在,查询次数为{num}";
        }