Java Program To Search For A Range In Sorted Array
We need to find first and last positions of an element in a sorted array. In case element is not present, we need to return [-1, -1].
Input: A = [5, 7, 7, 8, 8, 10] B = 8 Output: [3, 4]
This is an interview question which is asked in companies like Google & Microsoft. You can find the question in popular sites like InterviewBit & LeetCode.
We can use modified version of binary search to find the range of the element. For leftmost element, we should move left side even when we find B & keep on updating the leftmost position. Same goes for rightmost element. In that case we need to keep on moving towards right side even when we encounter B.
We are doing two binary searches, so overall time complexity would be O(log n).
Here is the fully working Java solution of the problem.