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

VH
Answered by Vlad H. Computing tutor

772 Views

See similar Computing University tutors

Related Computing University answers

All answers ▸

What is polymorphism in regards to Object Oriented Programming (OOP)? Provide an example.


Write a recursive binary search algorithm in pseudocode.


What is the purpose of RAM in a computer?


What is inheritance in object-oriented programming?


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–2025

Terms & Conditions|Privacy Policy
Cookie Preferences