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.

#Bisectional search (return one of the locations)
def bisectioanl_search(L,k, low, high):
 if high>=low:
 mid = (low + high) // 2
 if L[mid]==k:
 return mid
 elif L[mid]>k:
 return bisectioanl_search(L,k,low,mid-1)
 else:
 return bisectioanl_search(L, k, mid+1,
high)
 else:
 return -1
L=[2,5,8,12,15,15,19,21,26,36,39,41,45,50,53]
k=15
print(bisectioanl_search(L,k,0,len(L)))

NOTE: This program should need to be done in Python programming

Answer 1

#Bisectional search (return one of the locations)

def bisectioanl_search(L,k, low, high):
 if high>=low:
  mid = (low + high) // 2
  if L[mid]==k:
    return mid
  elif L[mid]>k:
    return bisectioanl_search(L,k,low,mid-1)
  else:
    return bisectioanl_search(L, k, mid+1,high)
 else:
  return -1

if __name__ == "__main__":
  indexes = []
  L=[2,5,8,12,12,12,12,15,15,19,21,26,36,39,41,45,50,53]
  k=12
  while True :
    val = bisectioanl_search(L,k,0,len(L))
    if val==-1:
      break
    else:
      L.pop(val)
      if indexes:
        new = max(indexes)
        indexes.append(new+1)
      else:
        indexes.append(val)
     
  ind = ','.join([str(x) for x in indexes])
  if ind:
    print("The element",k,"was found in",ind,"location(s).")
    print("The element",k,"appeared in the list",len(indexes),"times.")
  else:
    print("The element",k,"not found")

If you want to use reccursion than we can't modify the function as it is calling itself again and again instead we can do a trick to append the indexes in a list everytime it gets the index of the key and call the same function after deleting the index value. As it will always a sorted array to the same value indexes should be in increasing order.

There is another way wothout reccursion. You can do either of them.

def bisectional_search(lst,x,l,r): 
    loc = []
    while l <= r: 
        mid = l + (r - l) // 2; 
          
        # Check if x is present at mid 
        if lst[mid] == x:
            lst.pop(mid)
            if loc:
              new = max(loc) #max of index+1
              loc.append(new+1)
            else:
              loc.append(mid)
  
        # If x is greater, ignore left half 
        elif lst[mid] < x: 
            l = mid + 1
  
        # If x is smaller, ignore right half 
        else: 
            r = mid - 1
    if loc:
      return loc
    else:
      return -1 #not present
  
# Driver Code 
L=[2,5,8,12,15,15,15,19,21,26,36,39,41,45,50,53]
k=15
# Function call 
result = binarySearch(L, 0, len(arr), k)
if result != -1: 
    ind = ','.join([str(p) for p in result]) 
    print ("Element is present at index ", ind) 
    print ("Element is present in the list ", len(result),"times")
else: 
  
    print ("Element is not present in array") 

Any query you can as in the comment.