Question

Consider following Bisectional search implementation that prints the location of the elements found in a given sorted list. If not found it prints

-1. Modify the program such that it would provide:

• All the places in the list where the element was found

• How many times the element appeared in the list.

NOTE

Answer should be in python.

Answer 1

Ans: Both the sub-parts are solved using a single python program with binary search algorithm. Please read comments in the program to get a better understanding.

# Binary Search
def bisect(arr, key, getFirstOccurence):

    # Initial search area 
    low = 0 
    high = len(arr) - 1

        # Initialize the result by -1
    result = -1

    while low <= high:
        # Find the mid value in the search area
        mid = low + (high-low) // 2

        # If key is found, update the result
        if key == arr[mid]:
            result = mid

            # Search in the lower half to find first occurence
            if getFirstOccurence:
                high = mid - 1
            # Search in the upper half to find last occurence
            else:
                low = mid + 1

        # If key is less than the middle element, search in lower half
        elif key < arr[mid]:
            high = mid - 1
        # If key is more than the middle element, search in upper half
        else:
            low = mid + 1

    # Return the index if found or -1 if the element is not found
    return result


# Driver function
if __name__ == '__main__':

    arr = [2, 5, 5, 5, 6, 6, 8, 9, 9, 9]
    key = int(input())

    first = bisect(arr, key, True)  # True to find first occurrence
    last = bisect(arr, key, False)  # False to find last occurrence

    count = last-first+1

    if first != -1:

        # 0-based indexes
        print("1. All Occurences:", end = " ")
        while first<=last:
            print(str(first), end = " ")
            first += 1

        # Printing count in a new line
        print()
        print("2. Count: "+str(count))

    else:
        # Print -1 if not found
        print(str(-1))