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?