Find a given element m in a list of n sorted numbers, with time complexity O(log(n))

An implementation of the Binary Search algorithm will be sufficient. The algorithm works as follows:Position on the middle element in the list of numbers. If the current number is equal to the given number then return current position. Otherwise: If the current number is larger than the target element then repeat this procedure on a subset of the provided list with range: 0 to current_index - 1, where current_index - 1 will become a right iteration boundary. If the current number is smaller than the target element then repeat this procedure on a subset of the provided list with range: current_index + 1 to n where current_index + 1 will become a left iteration boundary.When the left boundary is greater than or equal to the right boundary exit (element is not in the list).Code:import math t = input() # Read target elems = [int(x) for x in input().split()] # Read list of numbers index = binary(0, len(elems) - 1, elems, t) # Index of element def binary(left_boundary, right_boundary, elems, t): m = math.floor((left_boundary + right_boundary) / 2) if elems[m] == t: return m elif t < elems[m]: return binary(left_boundary, m - 1, elems, t) elif t > elems[m]: return binary(m + 1, right_boundary, elems, t) else: return -1 # Target not in list

Related Computing University answers

All answers ▸

What is inheritance in object-oriented programming?


Write a recursive binary search algorithm in pseudocode.


What is the purpose of RAM in a computer?


Given two strings s1 and s2 return the location of each permutation of the s1 string within the s2 string.


We're here to help

contact us iconContact usWhatsapp logoMessage us on Whatsapptelephone icon+44 (0) 203 773 6020
Facebook logoInstagram logoLinkedIn logo

© MyTutorWeb Ltd 2013–2024

Terms & Conditions|Privacy Policy