Sharon is working on a sorted array of integers and wants to determine the count of elements that are less than or equal to a specific key. As her supportive programmer, you are tasked with creating a program to assist Sharon in counting the number of elements that meet this criterion (less than or equal to the given key) using the binary search technique.Input format :The first line of input consists of an integer N, representing the size of the array.The second line consists of N space-separated integers, the elements of the array.The third line consists of an integer key, the value to search for in the array.Output format :The output prints a single integer, representing the count of elements that are less than or equal to the given key.
Question
Sharon is working on a sorted array of integers and wants to determine the count of elements that are less than or equal to a specific key. As her supportive programmer, you are tasked with creating a program to assist Sharon in counting the number of elements that meet this criterion (less than or equal to the given key) using the binary search technique.Input format :The first line of input consists of an integer N, representing the size of the array.The second line consists of N space-separated integers, the elements of the array.The third line consists of an integer key, the value to search for in the array.Output format :The output prints a single integer, representing the count of elements that are less than or equal to the given key.
Solution
Sure, here is a Python solution for the problem:
def count_elements(arr, key):
low = 0
high = len(arr) - 1
while low <= high:
mid = low + (high - low) // 2
if arr[mid] <= key:
low = mid + 1
else:
high = mid - 1
return low
# Input
N = int(input())
arr = list(map(int, input().split()))
key = int(input())
# Output
print(count_elements(arr, key))
This program works by performing a binary search on the sorted array. It starts by setting low to the first index of the array and high to the last index. Then, it enters a loop where it calculates the middle index mid and checks if the element at mid is less than or equal to the key. If it is, it moves low to mid + 1, effectively discarding the lower half of the array. If it's not, it moves high to mid - 1, discarding the upper half. This process continues until low is greater than high, at which point the function returns low, which is the count of elements less than or equal to the key.
Similar Questions
Alex 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.
Given a sorted array A of size N, along with an integer target K, implement Binary Search to find the target K in the given array.Input FormatThe first line of input contains an integer N - the size of an array and target K. The second line contains the elements of the array.Output FormatFor each iteration of Binary Search, print the values of low, high, and mid. At the end, if the target K is found in the array, print "True" otherwise, print "False".Constraints1 <= N <= 201 <= A[i] <= 103ExampleInput 19 121 4 6 7 10 11 12 20 23Output 10 8 45 8 6TrueInput 210 213 5 8 11 15 17 19 23 26 30Output 20 9 45 9 75 6 56 6 6False
Program to demonstrate the use of Binary Search to search a given element in a sorted array in ascending order.
Arun is tasked with developing a binary search algorithm to efficiently locate the index of the first occurrence of a number divisible by 3 in a given sorted array of integers. Write a program to help Arun navigate the array elements and locate the required index. If a number divisible by 3 is found, return its index; otherwise, gracefully handle the absence of such a number.Input format :The first line consists of an integer n, representing the size of the array.The second line consists of n space-separated integers representing the elements of the sorted
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.