Array/List 中的多重二分搜索

Question

这是执行二分查找的常用程序

def binary_search(lst,num):
    fl=0
    low=0
    high=len(lst)
    while low<=high :
        mid=int((low+high)/2)
        if lst[mid]==num :
            fl=1
            print ('Number Found at index:',mid)
            break
        elif lst[mid]>num :
            low=mid+1
        else :
            high=mid-1
    if fl==0 :
        print ('Number Not Found')
lst=eval(input("Enter a sorted list:")
num=int(input("Enter a number to find:")
binary_search(lst,num)

问题
list/array
中出现次数超过1次的元素的索引要搜索打印怎么办 示例： 列表= [1,1,1,2,3,4,5]
我想搜索 1，它出现了 3 次，所以我想打印所有 3 个索引，例如：-

在索引处找到的编号：0
在索引处找到的数字：1
在索引处找到的数字：2

（二进制搜索是强制性的）

Answer 1

这段代码应该可以满足您的要求：

def binary_search(lst, num):
    element_found = False
    low = 0
    high = len(lst)
    while low <= high:
        mid = (low + high) // 2
        if lst[mid] == num:
            # Here you have found your element. If the list has several times this values, it will be the neighbours
            element_found = True
            find_equal_neighbours(lst, mid)
            break
        elif lst[mid] < num:
            low = mid + 1
        else:
            high = mid - 1
    if not element_found:
        print('Number Not Found')


def find_equal_neighbours(lst, index):
    low_index = index
    high_index = index
    value = lst[index]
    while low_index - 1 >= 0 and lst[low_index - 1] == value:
        low_index -= 1
    while high_index + 1 < len(lst) and lst[high_index + 1] == value:
        high_index += 1
    for i in range(low_index, high_index + 1):
        print('Number Found at index:', i)


lst = [1, 1, 1, 3, 4, 5]
num = 1
binary_search(lst, num)

一旦您通过二分查找找到了您想要的元素，如果列表中有其他具有相同值的元素，它们将紧挨着您的元素（因为这是一个排序列表）。函数 find_equal_neigbours(lst, index) 打印等于列表 lst.

中索引 index 处的元素的 neigbhours 值的所有索引

它打印：

Number Found at index: 0
Number Found at index: 1
Number Found at index: 2

Array/List 中的多重二分搜索

Multiple Binary Search in Array/List

python

loops

arraylist

binary-search

python-3.x