当前位置:首页 > 数据结构与算法 > 正文内容

二分查找

admin4年前 (2020-11-29)数据结构与算法2870

使用二分法对数组进行元素的搜索,返回查找的元素索引,当然使用二分搜索的前提是数组已经完成排序。原始数组有10个元素,要搜索的元素是11。

整个排序过程如下:

首先原始数组如下:

二分法1.jpg

第一次两个指针位置如下:

二分法2.jpg

低指针和高指针分别指向数组元素的最低处和最高处,也就是指向索引0位置和索引 length-1处,中点指向(low + high)/ 2位置(此时mid指向的值为4.5,向下取整得到4)。此时mid处指向的元素大小为9,小于11,所以将low指针指向此时的mid + 1位置,mid指向(low + high)/ 2位置。如下图:

第二次两个指针位置:

二分法3.jpg

此时mid指向的元素为13,大于11,所以high指向mid-1处,mid指向(low + high)/ 2处。如下图:

二分法4.jpg

此时mid和low重合了,不过没关系,仍然重复上面的步骤,mid指向的元素为10.小于11.所以low指向mid + 1位置,此时low、mid、high三者都重合了,比较mid与11,此时相等了,返回此时的索引也就是mid,完成搜索。

这个过程的python代码如下(部分来自算法图解):

# -*- coding: utf-8 -*-
"""
Created on Sun Nov 29 16:05:51 2020

@author: cyhu
"""


def binarySearch(list, item):
    """
    
    Parameters
    ----------
    list:
        以list的形式输入数据.
    item:
        要搜索的元素.

    Returns
    -------
    return : 
        搜索结果,返回搜索到的索引或者返回None.

    """
    low = 0
    high = len(list) - 1
    
    while(low <= high):
        mid = (low + high) // 2
        guess = list[mid]
        
        if guess == item:
            return mid
        elif guess > item:
            high = mid - 1
        elif guess < item:
            low = mid + 1

    return None

if __name__ == "__main__":
    list = [2,5,7,8,9,10,11,13,15,20]
    result = binarySearch(list, 11)
    print(result)

 

 

扫描二维码推送至手机访问。

版权声明:本文由lovedm.club发布,如需转载请注明出处。

本文链接:http://lovedm.club/?id=106

分享给朋友:
返回列表

上一篇:单链表

下一篇:C# 二叉树

“二分查找” 的相关文章

单链表

单链表

单链表存储一个直接后继的地址,用一组任意的存储单元存储线性表中的元素。数据域(数据元素)+指针域(指示后继元素存储位置) = 结点,如下图:a和b是两个结点,其中a的指针域保存了指向b的地址。以结点的序列表示线性表 称为链表以线性表中第一个数据元素a1的存储地址作为线性表的地址,称作线性表的头指针。...

C# 二叉树

C# 二叉树

这里实现了二叉树的创建与插入结点,前中后序遍历的递归实现以及前序遍历的非递归实现,层序遍历的非递归实现。插入结点时采用二叉排序树的方式,没有处理有相同结点时的情况,按下面代码中插入结点时,构成的二叉树如下:using System; using System.Collectio...

以层序插入二叉树结点

这里以层序插入二叉树的结点,以先序遍历输出。上一篇关于二叉树的内容在这里:http://lovedm.club/?id=110using System; using System.Collections.Generic; namespace BTree {...

中缀表达式转后缀表达式

中缀表达式转后缀表达式

转换过程如下:1、运算数:直接输出;2、左括号:压入堆栈;3、右括号:将栈顶的运算符弹出并输出,直到遇到左括号(出栈,不输出);4、运算符:若优先级大于栈顶运算符时,则把它压栈;若优先级小于等于栈顶运算符时,将栈顶运算符弹出并输出;再比较新的栈顶运算符,直到该运算符大于栈顶运算符优先级为止,然后将该...