[快学Python3]二分查找[策略优化版本]

概述

在上文《二分查找》中,我们了解了二分查找基本实现原理和具体的实现算法。

但大家有没有发现,如果目标查找值,如果在查找序列中存在多个,则查找返回的索引值,会有所变化。

那下面我们试着利用二分查找实现以下功能:

  • 查找目标值在序列中第一次出现时的索引
  • 查找目标值在序列中最后一次出现时的索引

例如,有序列如下:

seq = [1, 2, 3, 4, 5, 5, 5, 5, 6, 7, 8]

我们查找目标值: 5

  • 第一次出现在索引为:4 的位置
  • 最后一次出现在索引为:7 的位置

下面我们对二分查找算法进行策略改造升级为:

# 用于实现二分查找第一次出现的算法
first_binary_search(seq, query)

# 用于实现二分查找最后一次出现的算法
last__binary_search(seq, query)

代码实现

first优先策略算法实现

# -*- coding:utf-8 -*-

__author__ = '苦叶子'

# first二分查找算法
# seq   待查序列
# query 要查找的目标
def first_binary_search(seq, query):    
    # start为起始索引
    # end  为结束索引
    start, end = 0, len(seq) - 1

    while start <= end:
        mid = start + (end - start) // 2  # // 整除
        if (mid == 0 and seq[mid] == query) or
             (seq[mid] == query and seq[mid-1] < query):            
            # 这是实现first的最关键判断 
            # 在seq中找到目标query第一次出现的位置
            # 返回对应的索引值
            return mid
        elif seq[mid] < query:            
            # 目标值大于中间值
            # 说明目标值在mid - end之间
            start = mid + 1
        else:            
            # 目标值小于于中间值
            # 说明目标值在start - mid之间
            end = mid - 1

    # 目标值不存在于seq中,返回None
    return None

if __name__ == "__main__":    
    print("二分查找first示例")    
    print("二分查找只适合有序的序列")

    seq = [1, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 8, 10, 13, 15]    
    
    # 返回7
    print("5第一次出现的索引位置为: ", first_binary_search(seq, 5))    
    
    # 返回13
    print("7第一次出现的索引位置为: ", first_binary_search(seq, 7))    

    # 返回15
    print("8第一次出现的索引位置为: ", first_binary_search(seq, 8))

last优先策略算法实现

# -*- coding:utf-8 -*-


__author__ = '苦叶子'
    
# last二分查找算法
# seq   待查序列
# query 要查找的目标
def last_binary_search(seq, query):    
    # start为起始索引    # end  为结束索引
    start, end = 0, len(seq) - 1

    while start <= end:
        mid = start + (end - start) // 2  # // 整除
        if (seq[mid] == query and mid == len(seq) - 1) or 
            (seq[mid] == query and seq[mid+1] > query):            
            # 这是实现last的最关键判断 
            # 在seq中找到目标query第一次出现的位置
            # 返回对应的索引值
            return mid
        elif seq[mid] < query:            
            # 目标值大于中间值
            # 说明目标值在mid - end之间
            start = mid + 1
        else:            
            # 目标值小于于中间值
            # 说明目标值在start - mid之间
            end = mid - 1

    # 目标值不存在于seq中,返回None
    return None

if __name__ == "__main__":    
    print("二分查找last示例")    
    print("二分查找只适合有序的序列")

    seq = [1, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 8, 10, 13, 15]    
    
    # 返回9
    print("5最后一次出现的索引位置为: ", last_binary_search(seq, 5))    
    
    # 返回14
    print("7最后一次出现的索引位置为: ", last_binary_search(seq, 7))    
    
    # 返回15
    print("8最后一次出现的索引位置为: ", last_binary_search(seq, 8))

原文发布于微信公众号 - 开源优测(DeepTest)

原文发表时间:2017-12-17

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

51Nod 1090 3个数和为0(暴力)

1090 3个数和为0 基准时间限制:1 秒 空间限制:131072 KB 分值: 5         难度:1级算法题 给出一个长度为N的无序数组,数组中的元...

27360
来自专栏C语言及其他语言

【每日一题】问题 1472: 矩阵乘法

关注我们 题目描述 给定一个N阶矩阵A,输出A的M次幂(M是非负整数) 例如: A = 1 2 3 4 A的2次幂 7 10 ...

334100
来自专栏数据结构与算法

P2590 [ZJOI2008]树的统计

题目描述 一棵树上有n个节点,编号分别为1到n,每个节点都有一个权值w。 我们将以下面的形式来要求你对这棵树完成一些操作: I. CHANGE u t : 把结...

29460
来自专栏数据结构与算法

洛谷P3391 【模板】文艺平衡树(Splay)

题目背景 这是一道经典的Splay模板题——文艺平衡树。 题目描述 您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:翻转一个区...

379110
来自专栏尾尾部落

[算法总结] 二分查找

二分查找法作为一种常见的查找方法,将原本是线性时间提升到了对数时间范围,大大缩短了搜索时间,但它有一个前提,就是必须在有序数据中进行查找。

22920
来自专栏desperate633

LintCode 搜索插入位置题目分析代码

给定一个排序数组和一个目标值,如果在数组中找到目标值则返回索引。如果没有,返回到它将会被按顺序插入的位置。 你可以假设在数组中无重复元素。

8620
来自专栏机器学习从入门到成神

2013百度校招笔试真题以及解析(二)

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

10510
来自专栏尾尾部落

[剑指offer] 调整数组顺序使奇数位于偶数前面

输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相...

10820
来自专栏desperate633

LintCode 恢复旋转排序数组题目分析代码

说明 什么是旋转数组? 比如,原始数组为[1,2,3,4], 则其旋转数组可以是[1,2,3,4], [2,3,4,1], [3,4,1,2], [4,1,...

9220
来自专栏机器之心

入门 | 数据科学初学者必知的NumPy基础知识

选自TowardsDataScience 作者:Ehi Aigiomawu 机器之心编译 参与:李诗萌、路 本文介绍了一些 NumPy 基础知识,适合数据科学初...

28630

扫码关注云+社区

领取腾讯云代金券