Example: Finding an element from a sorted array
Let's say we have an algorithm that accepts a sorted array of length N as its input. Then in each iteration it randomly selects an element from the array and performs the following operation:
if (value == A[randomIndex])
// element found
else if (value < A[randomIndex])
// check the left subarray of the randomIndex
else
// check the right subarray of the randomIndex
This is similar to binary search but instead of selecting a mid index of the low and high index, we simply select a random index between low and high index.
Can anyone please provide the time complexity for this algorithm in worst, average and best case with a simple explanation for each?