Question

translate the binary search and insertion algorithm into a subprogram BINARY(ARRAY,LB,UB,ITEM,LOC) which finds either the location LOC where ITEAM appears in ARRAY or the location LOC where ITEAM should be inserted into Array using python

Answer 1

SOLUTION TO THE ABOVE QUESTION

SOLUTION CODE

#defining a function to search an item given an array
def binarySearch(ARRAY,LB, UB,ITEM ):
    # Check base case
    if UB >= LB:
        mid = LB + (UB - LB) // 2

        # If element is present at the middle itself
        if ARRAY[mid] == ITEM:
            return mid

        # If element is smaller than mid, then it
        # can only be present in left sub array
        elif ARRAY[mid] > ITEM:
            return binarySearch(ARRAY, LB, mid - 1, ITEM)

        # Else the element can only be present
        # in right subarray
        else:
            return binarySearch(ARRAY, mid + 1, UB, ITEM)

    else:
        # Element is not present in the array
        return -1

#We define a method which returns the index to insert an item
def binary_insertion(ARRAY, ITEM):
   left, right = 0, len(ARRAY) - 1
   ans = 0
   while left <= right:
      mid = (left + right) // 2
      if ITEM >= ARRAY[mid]:
         ans = mid + 1
         left = mid + 1
      else:
         right = mid - 1
   return ans

#Now lets wite the driver code
ARRAY = [2, 3, 4, 10, 40,45, 70,90]

print("This is the available array: "+str(ARRAY))
print("Enter the operation to perform: ")
print("1. Search an item")
print("2.Insert an item")
option = int(input("Enter your option: "))
if option==1:
    search_item = int(input("Enter the item to search: "))
    # Function call
    serch_index = binarySearch(ARRAY, 0, len(ARRAY) - 1, search_item)
    if serch_index != -1:
        print("Element is present at index % d" % serch_index)
    else:
        print("Element is not present in array")
elif option == 2:
    insert_item = int(input("Enter the item to insert: "))
    my_insert_index = binary_insertion(ARRAY, insert_item)
    print("The item "+str(insert_item)+" will be inserted at index "+str(my_insert_index))

else:
    print("Invalid option, please try again")

SAMPLE OUTPUT PROGRAM