Locate the first or last instance of a specified number in a sorted array.

The goal is to create a function that identifies the first or last occurrence of a specific number, referred to as X, within a sorted array. This means the function will traverse the provided sorted array to locate either the first or last appearance of the number X and return the corresponding index. It's important to note that since the array is sorted, there could be multiple instances of X, so you should continue searching even after locating the first occurrence, particularly if you're aiming to find the last occurrence. Keep these important points in mind: The array is sorted, which enables the use of binary search for better efficiency. The function must return the index of either the first or last occurrence. If the number is not present in the array, the function should reflect that as well.

An effective approach to solve this issue is to implement a modified version of Binary Search. For instance, if we have a sorted array like [1, 3, 5, 5, 5, 6, 8, 9] and we aim to locate the first instance of 5. Below is a Python code snippet to achieve that: def findFirst ( arr , low , high , key ) : if high >= low : mid = low + ( high - low ) // 2 if ( mid == 0 or key > arr [ mid - 1 ] ) and arr [ mid ] == key : return mid elif key > arr [ mid ] : return findFirst ( arr , ( mid + 1 ) , high , key ) else : return findFirst ( arr , low , ( mid - 1 ) , key ) return - 1 # test array arr = [ 1 , 3 , 5 , 5 , 5 , 6 , 8 , 9 ] key = 5 print ( "First occurrence of " , key , " is found at index: " , findFirst ( arr , 0 , len ( arr ) - 1 , key ) ) The function findFirst in the code utilizes binary search to locate the key within the array. It begins by examining the middle element. If the target key exceeds the middle element, it deduces that the key must be in the right half of the array, prompting a search there. Conversely, if the key is smaller than the middle element, it checks the left half of the array. This method effectively halves the search space with each iteration, resulting in a time complexity of O(log n).

To locate the last occurrence of the number 5 in the same array, we can adjust the function as follows: def findLast ( arr , low , high , key , n ) : if high >= low : mid = low + ( high - low ) // 2 if ( mid == n - 1 or key < arr [ mid + 1 ] ) and arr [ mid ] == key : return mid elif key < arr [ mid ] : return findLast ( arr , low , ( mid - 1 ) , key , n ) else : return findLast ( arr , ( mid + 1 ) , high , key , n ) return - 1 n = len ( arr ) print ( "Last occurrence of " , key , " is found at index: " , findLast ( arr , 0 , n - 1 , key , n ) ) In this code, we maintain the index of the "found" key while searching the array and continue searching towards the right half even after locating the key. This allows us to identify the last occurrence of the key.