精华内容
下载资源
问答
  • python二分查找

    2019-10-16 18:57:41
    python二分查找的相关代码二分查找 二分查找 二分查找是非常基本的算法题,一定要能熟练写出 def myBinarySearch(arr,target): ##边界检查 if len(arr) < 1: return -1 ##注意数组的左右边界 lo = 0 high ...

    python二分查找的相关代码

    二分查找

    二分查找是非常基本的算法题,一定要能熟练写出

    def myBinarySearch(arr,target):
    	##边界检查
        if len(arr) < 1:
            return -1
        ##注意数组的左右边界
        lo = 0
        high = len(arr) - 1
        
        ##为什么市lo <= high是因为我们要比较到数组只有一个元素,这个时候lo == high,此时 mid == lo == high,这个时候arr[mid] != target,说明查找失败
        while lo <= high:
            mid = (lo + high) // 2
            if arr[mid] == target:
                return mid
            elif arr[mid] < target:
                lo = mid + 1
            else:
                high = mid - 1
        return -1
        
    

    找出大于等于目标值的最小索引

    def my_lower_bound(arr,target):
    	##边界检查
        if len(arr) < 1:
            return -1
        lo = 0
        high = len(arr) - 1
        ##注意这里为什么是 <,因为最后循环结束的时候只能lo == high,并且mid == high == lo,?arr[mid] >= target
        while lo < high:
            mid = (lo + high) // 2
            ## target 比中间之要小,说明最小只在[mid+1,high]
            if arr[mid] < target:
                lo = mid + 1
            ##taget比中间值要大,考虑到重复值,high不能是mid - 1
            else:
                high = mid
        return lo
    
    

    返回大于目标值的最小索引(第一个大于目标值的索引)

    def my_upper_bound(arr,target):
        if len(arr) < 1:
            return -1
        lo = 0
        high = len(arr) - 1
        while lo < high:
            mid = (lo + high) // 2
            if arr[mid] <= target:
                lo = mid + 1
            else:
                high = mid
        return lo
    
    
    
    展开全文
  • Python 二分查找

    2021-03-24 10:50:11
    Python 二分查找 # binary_search import random def binary_search(array: list, value: int) -> bool: """ :param array: 有序列表 :param value: 查找的值 :return: """ array_length = len(array) # ...

    Python 二分查找

    # binary_search
    import random
    
    
    def binary_search(array: list, value: int) -> bool:
        """
        :param array: 有序列表
        :param value: 查找的值
        :return:
        """
        array_length = len(array)  # 数组长度
        start_index, end_index = 0, array_length - 1  # 每次二分的开始和起始值
        while start_index.__le__(end_index):  # 当开始值小于等于起始值的时候说明还没有判断完
            mid_index = (start_index + end_index) // 2  # 定义列表的中间索引
            if value.__eq__(array[mid_index]):  # 判断value是否和中间值相等
                return True  # 相等返回True
            elif value.__lt__(array[mid_index]):  # value小于中间值 说明value有可能在列表的左边
                end_index = mid_index - 1  # 将结束的索引重新定义 并且不包含索引为mid_index的值 结束的索引为上一次中间索引-1
            else:  # value大于中间值 说明value有可能在列表的右边
                start_index = mid_index + 1  # 将结束索引重新定义 并且包含索引为mid_index的值 结束索引为上一次中间索引+1
        return False  # 循环结束 说明value不在列表中 返回False
    
    
    if __name__ == '__main__':
        array = [i for i in range(100000000)]
        value = random.randint(0, 1000000)
        binary_search(array, value)
    
    
    展开全文
  • python 二分查找

    2020-03-13 16:14:47
    python 二分查找 # coding:utf-8 def binary_search(alist, item): """二分查找,递归""" n = len(alist) if n > 0: mid = n//2 if alist[mid] == item: return True eli...

    python 二分查找

    # coding:utf-8
    
    def binary_search(alist, item):
        """二分查找,递归"""
        n = len(alist)
        if n > 0:
            mid = n//2
    
            if alist[mid] == item:
                return True
            elif item < alist[mid]:
                return binary_search(alist[:mid], item)
            else:
                return binary_search(alist[mid+1:], item)
        
        return False
    
    if __name__ == "__main__":
        li = [17, 20, 26, 31, 44, 54, 55, 77, 93]
        print(binary_search(li, 55))
        print(binary_search(li, 100))
    
    展开全文
  • Python二分查找

    2020-12-07 16:06:53
    Python二分查找 # 返回 x 在 arr 中的索引,如果不存在返回 -1 def binarySearch (arr, l, r, x): # 基本判断 if r >= l: mid = int(l + (r - l)/2) # 元素整好的中间位置 if arr[mid] == x: ...

    Python二分查找

    # 返回 x 在 arr 中的索引,如果不存在返回 -1
    def binarySearch (arr, l, r, x): 
      
        # 基本判断
        if r >= l: 
      
            mid = int(l + (r - l)/2)
      
            # 元素整好的中间位置
            if arr[mid] == x: 
                return mid 
              
            # 元素小于中间位置的元素,只需要再比较左边的元素
            elif arr[mid] > x: 
                return binarySearch(arr, l, mid-1, x) 
      
            # 元素大于中间位置的元素,只需要再比较右边的元素
            else: 
                return binarySearch(arr, mid+1, r, x) 
      
        else: 
            # 不存在
            return -1
      
    # 测试数组
    arr = [ 2, 3, 4, 10, 40 ] 
    x = 10
      
    # 函数调用
    result = binarySearch(arr, 0, len(arr)-1, x) 
      
    if result != -1: 
        print ("元素在数组中的索引为 %d" % result )
    else: 
        print ("元素不在数组中")
    

    二分查找详细示意图

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,305
精华内容 1,322
关键字:

python二分查找

python 订阅