精华内容
下载资源
问答
  • 二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点:是要求待查表为有序表,且插入删除困难。使用场景:不经常变动而查找频繁的有序列表。 思想: 首先,假设表中元素是按升序排列,将表中间...
    二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点:是要求待查表为有序表,且插入删除困难。使用场景:不经常变动而查找频繁的有序列表。

    思想:

    首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,
    如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。

    二分查找(递归版)

    def binary_search(alist, item):
        """二分查找(递归版)"""
        n = len(alist)  # 获取列表长度
        if len(alist) == 0:  # 传入了一个空的列表,代表元素并未找到
            return False
        mid = n // 2
        if item == alist[mid]:
            return True  # 元素找到
        elif item < alist[mid]:
            # 元素在左半部分,递归调用
            return binary_search(alist[:mid], item)
        else:
            # 元素在右半部分,递归调用
            return binary_search(alist[mid + 1:], item)
    
    
    if __name__ == '__main__':
        alist = [0, 1, 2, 8, 13, 17, 19, 32, 42, ]
        print(binary_search(alist, 3))   # False 未找到
        print(binary_search(alist, 13))  # True  找到
            
    

    二分查找 (非递归版)

    
    def binary_search(alist, item):
        """二分查找 (非递归版)"""
        start = 0
        end = len(alist) - 1
        while start <= end:
            # 计算中间mid游标的值
            mid = (start + end)//2
            if item == alist[mid]:
                # 元素找到
                return True
            elif item < alist[mid]:
                # 元素在左半部分,递归调用
                end = mid -1
            else:
                # 元素在右半部分,递归调用
                start = mid + 1
        # 跳出循环,start>end表示元素不存在
        return False
    
    if __name__ == '__main__':
        alist = [0, 1, 2, 8, 13, 17, 19, 32, 42, ]
        print(binary_search(alist, 3))    # False 未找到
        print(binary_search(alist, 13))   # True  找到
        
    
    展开全文
  • # -*- coding:utf-8 -*- def binSearch( A, e):  lo = 0  hi = len(A)  while lo  mi = int((lo + hi )/2)  if A[mi] > e :  hi = mi   elif A[mi]
    # -*- coding:utf-8 -*-


    def binSearch( A, e):
        lo = 0
        hi = len(A)   
        while lo < hi :
            mi = int((lo + hi )/2)
            if A[mi] > e :
                hi = mi 
            elif A[mi] < e :
                lo = mi + 1
            elif A[mi] == e: 
                print(mi)
                break
        
        if A[mi] != e:
            print("对不起!没有找到%d"%e)
              
    if __name__=='__main__':
       A = [1,2,3,4,5,6,7,8,9,10]
       e = 3
       binSearch(A, e)
     








    展开全文
  • 以下使用python程序来随机生成一个20以内的不重复随机序列randlist,然后编写二分查找算法binary_search来查找目标target=8的索引。 import random N = 20 k = 10 randlist = sorted(random.sample(range(1,N), k)) ...

    二分查找算法,binary search algorithm,也称「折半搜索算法」、「对数搜索算法」

    它的使用前提:是一种在「有序数组」中查找某一特定元素的搜索算法。

    以下使用python程序来随机生成一个20以内的不重复随机序列randlist,然后编写二分查找算法binary_search来查找目标target=8的索引。

    import random
    N = 20
    k = 10
    randlist = sorted(random.sample(range(1,N), k))
    target = 8
    print(randlist)
    
    def binary_search(lst,tar):
    	left = 0
    	right = len(lst)-1
    	while right>=left:
    		mid = (left+right)//2
    		if tar == lst[mid]:
    			return mid
    		if tar > lst[mid]:
    			left = mid+1
    		else:
    			right = mid-1
    		print(lst[mid],left,right)
    	return -1
    print(binary_search(randlist,target))
    

    运行结果有随机性,取两种典型的结果如下:
    在这里插入图片描述
    此时,随机生成的列表中不含有8,所以返回-1
    在这里插入图片描述
    此时,在列表的3号位出现了8,所以返回了index3。

    当然,我们也可以使用递归的方法达到相同的效果,具体的代码如下:

    import random
    N = 20
    k = 10
    randlist = sorted(random.sample(range(1,N), k))
    target = 8
    print(randlist)
    
    def binary_search(lst,tar,left,right):
    	mid = (left+right)//2
    	if tar == lst[mid]:
    		return mid
    	if tar > lst[mid]:
    		left = mid+1
    	else:
    		right = mid-1
    	if left>right:
    		return -1
    	else:
    		return binary_search(lst,tar,left,right)
    print(binary_search(randlist,target,0,len(randlist)-1))
    
    展开全文
  • 对于一个有序数组,我们通常采用二分查找的方式来定位某一元素,请编写二分查找的算法,在数组中查找指定元素。 给定一个整数数组A及它的大小n,同时给定要查找的元素val,请返回它在数组中的位置(从0开始),若不...

    对于一个有序数组,我们通常采用二分查找的方式来定位某一元素,请编写二分查找的算法,在数组中查找指定元素。

    给定一个整数数组A及它的大小n,同时给定要查找的元素val,请返回它在数组中的位置(从0开始),若不存在该元素,返回-1。若该元素出现多次,请返回第一次出现的位置。

    测试样例:
    [1,3,5,7,9],5,3
    返回:1
    Java实现代码:

    import java.util.*;
    
    public class BinarySearch {
        public static int getPos(int[] A, int n, int val) {
            // 就是为了覆盖重复元素的出现的情况
            int high = n - 1, low = 0, mid = 0, flag = -1;
            // 如果最低位小于等于最高位一直循环
            while (low <= high) {
                mid = (high + low) / 2;
                // 如果中间值等于给定值就把这个位置给flag
                if (A[mid] == val) {
                    flag = mid;
                }
                // 如果中间值大于等于给定值,指针的最高位移动,之所以这里要用等于,
                // 就是因为此处会存在最低位出现重复元素的情况,比如4,4,10,21
                // mid第一次指向第二个4,但是第二个4并不是答案,所以high还需要移动,
                // 这样原先的flag的值就会被覆写。
                if (A[mid] >= val) {
                    high = mid - 1;
                }
                // 如果中间值小于给定值,最低位移动,此处是不可以用等号的,此处如果用等号
                // 就会导致第一个重复元素的下标为奇数(下标从0开始)的循环条件 low>high,
                // 最终结果错误。
                if (A[mid] < val) {
                    low = mid + 1;
                }
            }
            // 此处直接返回flag即可,不用做判断,如果数组中没有给定值,flag还是初始值-1;
            // 如果有给定值,flag进行了重新赋值,所以无需判断。
            return flag;
        }
    }
    

    Python3实现代码:

    print("有序数组中的二分查找")
    key=int(input("请输入您要查找的整数:"))
    c=[11,12,17,10,19,21,22,24,32,38,49,51,66,78,90]
    def BinarySearch(key,c):
        lo,hi= 0,len(c)-1
        while lo<=hi:
            #mid = int(lo+(hi-lo)/2)
            mid = int((lo+hi)/2)
            if key<=c[mid]:
                hi = mid-1
            elif key>=c[mid]:
                lo = mid+1
            else:
                return print("%s在数组中的索引为%s"%(key,mid))
        return print("%s不在该数组中"%key)
    
    BinarySearch(key,c)
    展开全文
  • python 7-3 查找指定字符 (15)

    千次阅读 2020-03-12 22:31:21
    本题要求编写程序,从给定字符串中查找某指定的字符。 输入格式: 输入的第一行是一个待查找的字符。第行是一个以回车结束的非空字符串(不超过80个字符)。 输出格式: 如果找到,在一行内按照格式“index = 下标...
  • 编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。该矩阵具有如下特性: 每行中的整数从左到右按升序排列。 每行的第一个整数大于前一行的最后一个整数。 示例 1: 输入: matrix = [ [1, 3, 5,...
  • 文章目录1.本章内容2.章节引言2.1 本书主要内容...编写第一种查找算法——二分查找 学习如何谈论算法的运行时间——大O表示法 了解一种常用的算法设计方法——递归 章节目录如下: 2.章节引言 2.1 本书主要内容 什么
  • 算法:二分查找

    2019-02-25 10:08:03
    标签:「算法」「二分查找」「大O表示法」 作者: MrLiuQ 审校: QiShare团队 前言:最近小编在看《算法图解》,将会总结一系列算法相关的文章。 关于算法的系列文章,小编将准备分“三步”来编写: 第一步:描述...
  • 导语:算法之路–二分查找 作者:变优秀的小白,Click 进入主页 爱好:Americano More Ice ! 算法上集: 算法图解(一) 数组与链表 前提知识 大家是否还记得对数呢?你很可能不记得什么是对数了,但你大几率记得什么...
  • 编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true,否则返回 false。 链接:https://leetcode.com/problems/search-in-rotated-sorted-array-ii/ Suppose an array sorted in ascending order is ...
  • 首先,在数学上有一个经典的搜索算法,...第一步:编写一个二分查找法的小程序 import random #guessnumber.py #验证二分法查找法最多次数为logn "单轮测试结果" target = random.randint(1,1000)# 随机获得一个1-1000
  • 一、二分查找法 1.用Python3编写: def binary_search(list, item): # low 和 high 用于跟踪要在其中查找的部分 low = 0 high = len(list) - 1 # 只要范围没有缩小到只有一个元素,就继续循环 while low &...
  • 第3章-4 查找指定字符 (15 ) 本题要求编写程序,从给定字符串中查找某指定的字符。 欢迎加入python交流群:675489391(非补课班非教育机构,欢迎前来交流) 输入格式: 输入的第一行是一个待查找的字符。第行是...
  • LeetCode+算法+数据结构(write LeetCode with Python3) 相交链表.py 环形链表.py 环形链表II.py 删除链表中的节点.py 删除排序链表中的重复元素II.py ...二分查找(及其相关结构) 二分查找.py 搜索插入位
  • 本题要求编写程序,从给定字符串中查找某指定的字符。 输入格式: 输入的第一行是一个待查找的字符。第行是一个以回车结束的非空字符串(不超过80个字符)。 输出格式: 如果找到,在一行内按照格式“index = ...
  • 本题要求编写程序,从给定字符串中查找某指定的字符。 输入格式: 输入的第一行是一个待查找的字符。第行是一个以回车结束的非空字符串(不超过80个字符)。 输出格式: 如果找到,在一行内按照格式“index = 下标...
  • python 第3章-4 查找指定字符问题代码 问题 本题要求编写程序,从给定字符串中查找某指定的字符。 输入格式: 输入的第一行是一个待查找的字符。第行是一个以回车结束的非空字符串(不超过80个字符)。 输出格式:...
  • 本题要求编写程序,从给定字符串中查找某指定的字符。 输入格式: 输入的第一行是一个待查找的字符。第行是一个以回车结束的非空字符串(不超过80个字符)。 输出格式: 如果找到,在一行内按照格式“index = 下标...
  • 7-4 查找指定字符 (15) 本题要求编写程序,从给定字符串中查找某指定的字符。 输入格式: 输入的第一行是一个待查找的字符。第行是一个以回车结束的非空字符串(不超过80个字符)。 输出格式: 如果找到,在一行...
  • 本题要求编写程序,从给定字符串中查找某指定的字符。 输入格式: 输入的第一行是一个待查找的字符。第行是一个以回车结束的非空字符串(不超过80个字符)。 输出格式: 如果找到,在一行内按照格式“index = ...
  • 本题要求编写程序,从给定字符串中查找某指定的字符。 输入格式: 输入的第一行是一个待查找的字符。第行是一个以回车结束的非空字符串(不超过80个字符)。 输出格式: 如果找到,在一行内按照格式“index = ...
  • 查找和排序是最基本的算法,在很多脚本中都会...基本的查找方法有顺序查找、二分查找和分块查找等。其中,顺序查找是最简单的查找方法,就是按照数据排列的顺序依次查找,直到找到所查找的数据为止(可查看数据表都...
  • 本题要求编写程序,从给定字符串中查找某指定的字符。 输入格式: 输入的第一行是一个待查找的字符。第行是一个以回车结束的非空字符串(不超过80个字符)。 输出格式: 如果找到,在一行内按照格式“index = 下标...
  • 猜数游戏与二分查找 还记得猜数游戏吗?之前的问题是:如果你是攻击者,你能保证在10次(含)之内猜出对方的数字吗? 因为$2^{10} = 1024 > 1000$, 所以如果运用二分查找的话,我们作为攻击者是肯定可以赢得比赛...
  • python编写二分查找函数binary_search 二分法练习: 选择排序 数组和链表的优缺点 链表的优势、 链表的问题 常见的数组和链表操作的运行时间 需要在中间插入元素时,数组和链表哪个更好呢? 数组和链表哪个用...

空空如也

空空如也

1 2 3 4 5
收藏数 94
精华内容 37
关键字:

python编写二分查找

python 订阅