Implement Upper Bound
Learning 1D Array Binary Search DSA practice problem on Onlearn.
Difficulty: easy.
Topics: Finding the Upper Bound of a Value in a Sorted Array, Binary Search, Linear Search, Arrays, Time Complexity, Space Complexity, Loops, Conditional Statements, space complexity, optimization, array, search algorithms, binary search, time complexity analysis, Lower & Upper Bound, Algorithm Optimization.
Given a sorted array of N integers and an integer x, find the upper bound of x. The upper bound of an element x in a sorted array is defined as the smallest index ind such that arr[ind] x. If no such index exists (i.e., all elements are less than or equal to x), the upper bound is N (the size of the array). Input Format: The first line contains an integer N, the size of the array. The second line contains N space separated integers representing the elements of the array. The third line contains an integer x. Output Format: Print the upper bound of x. Examples: Example 1: Input: 4 1 2 2 3 2 Output: 3 Explanation: Index 3 is the smallest index such that arr[3] (which is 3) 2. Example 2: Input: 6 3 5 8 9 15 19 9 Output: 4 Explanation: Index 4 is the smallest index such that arr[4] (which is 15) 9.