4 篇笔记 写笔记

1. #0

   小花花

   124***[email protected]

   14

   '''二分查找有序不重复数组
   BinarySearch(unfinished).py'''
   # 未完成版
   def BinarySearch(sortedlist):
    num = int(input('Number:\t'))
    counter = 0 # 记录循环次数
    mid = 0 # 记录中间位置
    if num in [sortedlist[0], sortedlist[len(sortedlist) - 1]]: # 切割时取不到首尾
    print('Find it at beginning or end.')
    else:
    while True: # 切割数组
    mid = len(sortedlist) // 2
    if sortedlist[mid] == num:
    print('Find number {}.'.format(num))
    break
    elif sortedlist[mid] > num:
    sortedlist = sortedlist[:(mid + 1)]
    else:
    sortedlist = sortedlist[mid:]
    print(sortedlist, mid)
    counter += 1
    if counter > len(sortedlist) + 1: # 超过迭代次数即停止
    print('Don\'t find it.')
    break
   sortedlist = [-2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]
   BinarySearch(sortedlist)

   小花花

   124***[email protected]

   7年前 (2019年07月13日)
2. #0

   叫爸爸

   506***[email protected]

   55

   该算法的要求:

   • 1、必须采用顺序存储结构。
   • 2、必须按关键字大小有序排列。

   def bin_search(data_list, val): 
    low = 0 # 最小数下标 
    high = len(data_list) - 1 # 最大数下标 
    while low <= high: 
    mid = (low + high) // 2 # 中间数下标 
    if data_list[mid] == val: # 如果中间数下标等于val, 返回 
    return mid 
    elif data_list[mid] > val: # 如果val在中间数左边, 移动high下标 
    high = mid - 1 
    else: # 如果val在中间数右边, 移动low下标 
    low = mid + 1 
    return # val不存在, 返回None
   ret = bin_search(list(range(1, 10)), 3)
   print(ret)

   叫爸爸

   506***[email protected]

   7年前 (2020年01月09日)
3. #0

   ccneko

   ccn***@163.com

   8

   补充个增序或者减序都能用的版本:

   # 二分查找(非递归版本)
   # isAsc为True时,列表增序,否则减序
   def binarySearch(sortedList, key, isAsc=True):
    left = 0 # 查找范围最左边的下标
    right = len(sortedList) - 1 # 查找范围最右边的下标
    while left <= right: #
    mid = left + right >> 1 # 中间数下标(向下取整)
    if isAsc and sortedList[mid] < key \
    or not isAsc and sortedList[mid] > key: # key在中间数右边时,查找范围变为右边
    left = mid + 1
    elif isAsc and sortedList[mid] > key \
    or not isAsc and sortedList[mid] < key: # key在中间数左边时,查找范围变为左边
    right = mid - 1
    else:
    return mid # key为中间数时,返回其下标
    return -1

   ccneko

   ccn***@163.com

   6年前 (2020年02月26日)
4. #0

   东坡弃疾

   158***[email protected]

   11

   有序不重复数组,二分查找,非递归算法:

   def binaryserch(a,x):
    mid = tempmid =len(a) // 2 #mid 用于记录数组a的中间数,tempid 用于记录原始数组中mid的值
    while len(a) > 1:
    if a[mid] > x:
    a = a[:mid]
    mid = len(a) // 2 
    tempmid = tempmid - (len(a) - mid) 
    elif a[mid] < x:
    a = a[mid+1:]
    mid = len(a) // 2 
    tempmid = tempmid + mid +1
    else:
    break 
    if len(a) == 1:
    tempmid = tempmid if a[mid]== x else -1 
    if len(a) < 1:
    tempmid = -1 
    
    return tempmid

   东坡弃疾

   158***[email protected]

   6年前 (2020年07月21日)