Multiple Binary Search in Array/List

Question

This is the common program to perform binary search

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)

QUESTION
What should I do if I want to search and print the index of the element if it is present more than 1 times in the list/array
Example: List= [1,1,1,2,3,4,5]
I want to search 1 and it is present 3 times so I want to print all 3 indexes like:-

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

(BINARY SEARCH IS COMPULSORY)

Answer 1

This code should do what you are asking:

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)

Once you have found the element you want with the binary search, if the list has other elements with the same values, they will be next to your element (because this is a sorted list). The function find_equal_neigbours(lst, index) prints all the indexes of the neigbhours values equal to the element at the index index in the list lst.

It prints:

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