数据结构与算法学习笔记(python)——第5节 二分搜索

前言

本人是一个长期的数据分析爱好者，最近半年的时间的在网上学习了很多关于python、数据分析、数据挖掘以及项目管理相关的课程和知识，但是在学习的过程中，过于追求课程数量的增长，长时间关注于学习了多少多少门课程。事实上，学完一门课之后真正掌握的知识并不多，主要的原因是自己没有认真学习和理解温故而知新的这句话的真正含义。因此，从现在开始，我在学习《数据结构与算法——基于python》的课程内容之后，抽出固定的时间对每天学习的内容进行总结和分享，一方面有助于个人更好的掌握课程的内容，另一方面能和大家一起分享个人的学习历程和相应的学习知识。

第五节 二分搜索

1 顺序查找：
找到目标的第一个位置，如果找不到则返回-1；
程序

def bi_search_iter(alist, item):
    left, right = 0, len(alist) - 1
    while left <= right:
        mid = (left + right) // 2
        if alist[mid] < item:
            left = mid + 1
        elif alist[mid] > item:
            right = mid - 1
        else: # alist[mid] = item
            return mid
    return -1
num_list = [1,2,3,5,7,8,9]
print(bi_search_iter(num_list, 7))
print(bi_search_iter(num_list, 4))

输出结果

2 二分查找模板：
在刚开始学习写程序的时候，按照下面程序的思路体现四个重点内容，就可以解决百分之五十的二分查找难题；
程序

def binarysearch(alist, item):
    
    # 第一个重点 
    if len(alist) == 0:
        return -1 # 注意边界条件
    # 在碰到类似的情况时，将边界条件程序写上去；对运行时间没有影响；
    # 可以减少后续担心的情况；
    
    left, right = 0, len(alist) - 1
     # 第二个重点
        
    while left + 1 < right: # 当L和R相邻的时候，当L和R相等、R小于L的时候，跳出循环体；
        mid = left + (right - left) // 2
     # 第三个重点
        if alist[mid] == item:
            right = mid # 找到的首次出现的目标元素的位置；
        elif alist[mid] < item:
            left = mid
        elif alist[mid] > item:
            right = mid
   # 第四个重点
   # 退出循环之后，需要进行兜底的判断； 
   # 当L和R相邻，当L和R相等的时候，L和R都可能等于2，所以将目标元素和L和R相比，因为找第一个位置，所以将L放在前面 ；兜底
    if alist[left] == item:
        return left
    if alist[right] == item:
        return right
    return -1

3 在旋转有序数列中查找最小值
假设有一个升序排列的数列在某个未知节点处被前后调换，请找到数列中的最小值；
程序

# 方法1 
def searchlazy(alist): #O（nlgn）
    alist.sort() # 先排序
    return alist[0]# 返回第一个元素
# 方法2
def searchslow(alist):#O（n）
    mmin = alist[0]
    for i in alist:
        mmin = min(mmin, i)
    return mmin 
        
# 方法3
def search(alist):# O（lgn）
    if len(alist) == 0:
        return -1    # 第一个重点，先写边界条件
  
    # 第二个重点
    left, right = 0, len(alist) - 1
    while left + 1 < right: 
        if (alist[left] < alist[right]):# 如果数据有序，未被旋转；
            return alist[left];
    # 第三个重点
       mid = left + (right - left) // 2 
        if (alist[mid] >= alist[left]):# 前半部分有序，到后半部分去寻找
            left = mid + 1
        else:
            right = mid # 到前半部分去找
    # 第四个重点；兜底 L和R相邻，        
    return alist[left] if alist[left] < alist[right] else alist[right]

4 在旋转数组中查找
假设有一个升序排列的数列在某个未知节点处被前后调换，请找到目标值；
程序

#O（lgn）
def search(alist, target):
    if len(alist) == 0: # 第一个重点：初始条件的判断
        return -1    
    left, right = 0, len(alist) - 1
    while left + 1 < right: 
        mid = left + (right - left) // 2
         # 第二个重点：
        if alist[mid] == target:
            return mid
        
         # 第三个重点：
        if (alist[left] < alist[mid]):
            if alist[left] <= target and target <= alist[mid]: # 判断target是否在前半部分
                right = mid # 在前半部分寻找
            else:
                left = mid # 在后半部分寻找
        else: #与上面相反
            if alist[mid] <= target and target <= alist[right]:
                left = mid
            else: 
                right = mid
    # 第四个重点：兜底程序                        
    if alist[left] == target:
        return left
    if alist[right] == target:
        return right
    return -1

5 搜索插入位置
• 给定有序数组和一个目标值，如果在数组中找到此目标值则返回目标值的index，如果 没有找到，则返回目标值按顺序应该被插入的位置index.
• 注：可以假设数组中不存在重复数
程序

# 首先找到第一个大于等于target的数
def search_insert_position(alist, target):
    if len(alist) == 0: # 第一个重点
        return 0  
    left, right = 0, len(alist) - 1
    while left + 1 < right: #第二个重点
        mid = left + (right - left) // 2
        if alist[mid] == target:
            return mid 
      
    # 第三个重点
        if (alist[mid] < target):
            left = mid
        else:
            right = mid
    #  第四个重点：兜底       
    if alist[left] >= target:
        return left
    if alist[right] >= target:
        return right
       # 当L和R都小于target ，插入在最后；
    return right + 1

6 搜索区间
• 给一个有序、有重复数字的数组。找到给定目标值的开始和结束位置，如果目标数据不存在，返回（-1，-1）
思路
思路
首先运行找到第一个元素的程序，然后运行找到最后一个元素的程序；时间复杂度 O（lgn）
程序

# O（lgn）
def search_range(alist, target): # 第一个重点，base
    if len(alist) == 0:
        return (-1, -1)  
    
    lbound, rbound = -1, -1

    # search for left bound 
    left, right = 0, len(alist) - 1
    while left + 1 < right:  # 第二个重点
        mid = left + (right - left) // 2
        if alist[mid] == target: # 第三个重点
            right = mid
        elif (alist[mid] < target):
            left = mid
        else:
            right = mid
            
    if alist[left] == target: # 第四个重点 兜底程序
        lbound = left
    elif alist[right] == target:
        lbound = right
    else:
        return (-1, -1)

    # search for right bound 
    left, right = 0, len(alist) - 1        
    while left + 1 < right: 
        mid = left + (right - left) // 2 # 第二个重点
        if alist[mid] == target: # 第三个重点
            left = mid
        elif (alist[mid] < target): 
            left = mid
        else:
            right = mid
            
    if alist[right] == target: # 第四个重点
        rbound = right
    elif alist[left] == target:
        rbound = left
    else:
        return (-1, -1)        
    return (lbound, rbound)

7 在用空字符串隔的字符串的有序数列中查找
给定一个有序的字符串序列，这个序列中的字符串用空字符隔开，请写出找到给定字符串位置的方法；
思路
先从左往右或者从右往左找到非字符元素，然后再按照二分法，寻找mid，再将target和mid和寻找的非字符运输做比较，再决定mid向哪一端移动。
程序

# O（n） 可以用in逐项遍历
def search_empty(alist, target):
    if len(alist) == 0:
        return -1
      
    left, right = 0, len(alist) - 1
    
    while left + 1 < right:
        while left + 1 < right and alist[right] == "":  # 从右边开始找，找到第一个非空字符串，并将其位赋值给right
            right -= 1
        if alist[right] == "":
            right -= 1
        if right < left:
            return -1
        
        mid = left + (right - left) // 2
        while alist[mid] == "": # 当中间是空字符串时，向后寻找；
            mid += 1
            
        if alist[mid] == target:
            return mid
        if alist[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
            
    if alist[left] == target:
        return left
    if alist[right] == target:
        return right    
    return -1   

8 在无限序列中找到某元素的第一个出现位置
有序数据流
不知道序列长度
思路
先从左往右或者从右往左找到非字符元素，然后再按照二分法，寻找mid，再将target和mid和寻找的非字符运输做比较，再决定mid向哪一端移动。
程序

# 在有很多0的数组中找1出现的位置
def search_first(alist):
    left, right = 0, 1
    
    while alist[right] == 0:
        left = right
        right *= 2 # right变为2倍
        
        if (right > len(alist)):
            right = len(alist) - 1
            break
    
    return left + search_range(alist[left:right+1], 1)[0]

9 **供暖设备 **
• 冬季来临！你的首要任务是设计一款有固定供暖半径的供暖设备来给所有的房屋供 暖。
• 现在你知道所有房屋以及供暖设备在同一水平线上的位置分布，请找到能给所有房 屋供暖的供暖设备的最小供暖半径。
• 你的输入是每个房屋及每个供暖设备的位置，输出应该是供暖设备的最小半径
思路
先从左往右或者从右往左找到非字符元素，然后再按照二分法，寻找mid，再将target和mid和寻找的非字符运输做比较，再决定mid向哪一端移动。

转载：https://blog.csdn.net/qq_34740277/article/details/105316844