The “Ubiquitous Search Algorithm” would typically refer to a straightforward search method where we converge the search space till 'l' and 'r' points single element. If the middle location falls in the first pulse, the condition (A[m] < A[r]) doesn’t satisfy, we converge our search space to A[m+1 … r]. If the middle location falls in the second pulse, the condition (A[m] < A[r]) satisfied, we converge our search space to A[1 … m]. At every iteration we check for search space size, if it is 1, we are done.
What would you like to Propose?
The “Ubiquitous Search Algorithm” would typically refer to a straightforward search method where we converge the search space till 'l' and 'r' points single element. If the middle location falls in the first pulse, the condition (A[m] < A[r]) doesn’t satisfy, we converge our search space to A[m+1 … r]. If the middle location falls in the second pulse, the condition (A[m] < A[r]) satisfied, we converge our search space to A[1 … m]. At every iteration we check for search space size, if it is 1, we are done.
-> Worst-case performance Θ(N) -> Best-case performance O(1) -> Average-case performance Θ(log(N))
Issue details
We are handling the corner cases in the present in the Binary Search in more effecient way in Ubiquitous Binary Search.
Additional Information
No response