Write a program for binary search. The input will be the sorted file obtained as output of insertion sort or selection sort.The number to be searched should be given from the keyboard.The output will be the index of the location where the number is found. If the file contains unique numbers then a single index will be returned. If the file contains non-unique or duplicate numbers then the index of the first number in the list has to be returned.
Question
Write a program for binary search. The input will be the sorted file obtained as output of insertion sort or selection sort.The number to be searched should be given from the keyboard.The output will be the index of the location where the number is found. If the file contains unique numbers then a single index will be returned. If the file contains non-unique or duplicate numbers then the index of the first number in the list has to be returned.
Solution
Sure, here is a Python program for binary search:
def binary_search(arr, low, high, x):
if high >= low:
mid = (high + low) // 2
if arr[mid] == x:
return mid
elif arr[mid] > x:
return binary_search(arr, low, mid - 1, x)
else:
return binary_search(arr, mid + 1, high, x)
else:
return -1
arr = [2, 3, 4, 10, 40]
x = 10
result = binary_search(arr, 0, len(arr)-1, x)
if result != -1:
print("Element is present at index", str(result))
else:
print("Element is not present in array")
This program works by dividing the search space in 2 at every step. Starting with the whole array, it looks at the middle element: if the target value is equal to the current element, it returns the index. If the target value is less than the current element, it performs the search operation on the left half
Similar Questions
Write a program to perform binary search on a list of integers given below, to search for an element input by the user. If it is found display the element along with its position, otherwise display the message "Search element not found".5, 7, 9, 11, 15, 20, 30, 45, 89, 97
Program to demonstrate the use of Binary Search to search a given element in a sorted array in ascending order.
Select the correct statements among the following In the presence of duplicate elements in a list, binary search always finds the first occurrence of the element in the list In the presence of duplicate elements in a list, binary search may or may not find the first occurrence of the element in the list In the presence of duplicate elements in a list, the existing binary search algorithm with minor modifications can be used to find the first occurrence of the target element in the list In the presence of duplicate elements in a list , the existing binary search can be used to find any kth(k can be any number from 1 to number of times the element has been repeated) of target element in the list
Single File Programming QuestionProblem StatementAlex wants to create a program to search a target value in a sorted array. The program should input the array size and elements, as well as the target value. Utilizing binary search, it should determine if the target is present, and if so, provide the index. If not, display a message indicating its absence.Assist Alex in completing the program efficiently.Input format :The first line of input consists of an integer N, representing the size of the sorted array.The second line consists of N space-separated integers, the elements of the sorted array in ascending order.The third line consists of an integer target, the value to search for in the array.Output format :If the target is present in the array, print "The target value X is present at index Y", where X is the target element and Y is the index position (index starts from 0).If the target is not present, print "The target value X is not present in the array", where X is the target element.Refer to the sample output for formatting specifications.Code constraints :The given test cases will fall under the following constraints:2 ≤ N ≤ 101 ≤ elements ≤ 1000Sample test cases :Input 1 :514 29 37 48 5948Output 1 :The target value 48 is present at index 3Input 2 :10125 137 248 358 489 587 652 741 823 912850Output 2 :The target value 850 is not present in the array
Write a function that performs binary search on a sorted array.
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.