Implement Lower Bound
Learning 1D Array Binary Search DSA practice problem on Onlearn.
Difficulty: easy.
Topics: Finding the Lower Bound of x in a Sorted Array, Arrays, Binary Search, Linear Search, Time Complexity, Space Complexity, Big O Notation, Loops, Conditional Statements, space complexity, array, search algorithms, binary search, time complexity analysis, Lower & Upper Bound.
Lower Bound of an Element Problem Statement Given a sorted array of N integers and an integer x, find the lower bound of x. The lower bound algorithm finds the first or the smallest index in a sorted array where the value at that index is greater than or equal to a given key, x. In other words, find the smallest index ind such that arr[ind] = x. If no such index is found, return N (the size of the array). Input Specification N: An integer representing the size of the array. arr[]: A sorted array of N integers. x: An integer to find the lower bound for. Output Specification Return an integer representing the smallest index ind where arr[ind] = x. If no such index exists, return N. Sample Test Cases Example 1: Input: N = 4, arr[] = {1, 2, 2, 3}, x = 2 Output: 1 Explanation: Index 1 is the smallest index such that arr[1] = x (since arr[1] is 2, which is = 2). Example 2: Input: N = 5, arr[] = {3, 5, 8, 15, 19}, x = 9 Output: 3 Explanation: Index 3 is the smallest index such that arr[3] = x (since arr[3] is 15, which is = 9). No element before index 3 satisfies this condition. If no element were = 9, the answer would be 5.