Python中的二进制搜索（对分）-yiteyi-C++库

二进制搜索是一种用于在排序列表中搜索元素的技术。在本文中，我们将研究用于二进制搜索的库函数。 查找元素的第一次出现。

null

平分对分_left（a，x，lo=0，hi=len（a））：返回排序列表中x的最左侧插入点。最后两个参数是可选的，它们用于在子列表中搜索。

Python3

                         # Python code to demonstrate working                       
                         # of binary search in library                       
                         from                                     bisect                                     import                                     bisect_left                       
           
                         def                                     BinarySearch(a, x):                       
                                                 i                                     =                                     bisect_left(a, x)                       
                                                 if                                     i !                                     =                                     len                                     (a)                                     and                                     a[i]                                     =                                     =                                     x:                       
                                                 return                                     i                       
                                                 else                                     :                       
                                                 return                                     -                                     1                       
           
                         a                                     =                                     [                                     1                                     ,                                     2                                     ,                                     4                                     ,                                     4                                     ,                                     8                                     ]                       
                         x                                     =                                     int                                     (                                     4                                     )                       
                         res                                     =                                     BinarySearch(a, x)                       
                         if                                     res                                     =                                     =                                     -                                     1                                     :                       
                                                 print                                     (x, "                                     is                                     absent")                       
                         else                                     :                       
                                                 print                                     ("First occurrence of", x, "                                     is                                     present at", res)                       

输出：

First occurrence of 4 is present at 2

找到小于x的最大值。

Python3

                         # Python code to demonstrate working                       
                         # of binary search in library                       
                         from                                     bisect                                     import                                     bisect_left                       
           
                         def                                     BinarySearch(a, x):                       
                                                 i                                     =                                     bisect_left(a, x)                       
                                                 if                                     i:                       
                                                 return                                     (i                                     -                                     1                                     )                       
                                                 else                                     :                       
                                                 return                                     -                                     1                       
           
                         # Driver code                       
                         a                                     =                                     [                                     1                                     ,                                     2                                     ,                                     4                                     ,                                     4                                     ,                                     8                                     ]                       
                         x                                     =                                     int                                     (                                     7                                     )                       
                         res                                     =                                     BinarySearch(a, x)                       
                         if                                     res                                     =                                     =                                     -                                     1                                     :                       
                                                 print                                     ("No value smaller than ", x)                       
                         else                                     :                       
                                                 print                                     ("Largest value smaller than ", x, "                                     is                                     at index ", res)                       

输出：

Largest value smaller than  7  is at index  3

寻找最右边的事件

平分对分_right（a，x，lo=0，hi=len（a））返回排序列表a中x的最右插入点。最后两个参数是可选的，用于在子列表中搜索。

Python3

                         # Python code to demonstrate working                       
                         # of binary search in library                       
                         from                                     bisect                                     import                                     bisect_right                       
           
                         def                                     BinarySearch(a, x):                       
                                                 i                                     =                                     bisect_right(a, x)                       
                                                 if                                     i !                                     =                                     0                                     and                                     a[i                                     -                                     1                                     ]                                     =                                     =                                     x:                       
                                                 return                                     (i                                     -                                     1                                     )                       
                                                 else                                     :                       
                                                 return                                     -                                     1                       
           
                         a                                     =                                     [                                     1                                     ,                                     2                                     ,                                     4                                     ,                                     4                                     ]                       
                         x                                     =                                     int                                     (                                     4                                     )                       
                         res                                     =                                     BinarySearch(a, x)                       
                         if                                     res                                     =                                     =                                     -                                     1                                     :                       
                                                 print                                     (x, "                                     is                                     absent")                       
                         else                                     :                       
                                                 print                                     ("Last occurrence of", x, "                                     is                                     present at", res)                       

输出：

Last occurrence of 4 is present at 3

请参考二进制搜索用于编写自己的二进制搜索代码。 参考： https://docs.python.org/3/library/bisect.html

文章版权归作者所有，未经允许请勿转载。

THE END

Python