Question

1. Randomized Binary Search

Which are true of the randomized Binary Search algorithm?

Multiple answers:You can select more than one option

A) It uses a Variable-Size Decrease-and-Conquer design technique

B) Its average case time complexity is Θ(log n)

C) Its worst case time complexity is Θ(n)

D) It can be implemented iteratively or recursively

E) None of the above

2. Randomized Binary Search: Example

Assume you have an array, indexed from 0 to 9, with the numbers 1 4 9 16 25 36 49 64 81 100. You are searching for the key 100. Your random number generator gives the following numbers in range ​[0,9] to be used as indexes: 6 3 1 5 7 9 0 0 5 2 8 1 9 6 4 2 7. You consider those random numbers in order, ignoring those that have already been used or are outside the currently relevant range. How many key comparisons (i.e. comparing the search key of 100 against data in the array) will be required until you find the key 100? (Assume that <, =, or > can be determined with with a single key comparison.)

A) 1

B) 2

C) 3

D) 4

E) 5

F) 6

G) 7

H) 8

I) 9

J) 10

Short explanation would be appreciated.

Answer 1

Option A - It uses a Variable-Size Decrease-and-Conquer design technique. After every iteration, the jump size is decreased by 50% and in short 50% of the array is of no use anymore.

Option B - The average search time complexity is O(log n) as compared to linear search where the complexity is O(n).

Option C - The Worst time complexity is also O(log n) and not O(n), it would have been O(n) if the algorithm has to go through every element of the list or array and this won't be happening under any case.

Option D - The algorithm can be implemented both recursively and iteratively, using loops or maybe using recursion.

So, Options A, B, D are correct.

Here I am attaching a screenshot of the code of Randomized Binary Search for easier reference.

The code is well commented and can be easily understood.

1 #include <iostream> 2 #include <ctime> 3 using namespace std; 5 int getRandom(int x, int y) // generating a random number between x & y 7 srand(time(NULL)); 8 return (x + rand() % (y-x+1)); 9 } 10 11 int randomizedBinarySearch(int arr[], int i, int r, int x) // recursive binary search function 12 - { if (r >= 1) 13 int mid = getRandom(1, r); // middle as a random index between 1&r if (arr[mid] == x) // if element is present in the middle itself return mid; if (arr[mid] > x) // element smaller than mid so needs to be present in the left sub array return randomizedBinarySearch(arr, l, mid-1, x); return randomizedBinarySearch(arr, mid+1, r, x);// element will be present in the right sub array return -1; // element is not present 26 } 27 // Driver code 28 int main(void) 29 - { int arr[] = {1, 4, 9, 16, 25, 36, 49, 64, 81, 100}; int n = sizeof(arr)/ sizeof(arr[0]); int x = 100; int result = randomizedBinarySearch(arr, o, n-1, x); (result == -1)? printf("Element is not present in array") : printf("Element is present at index %d", result); return 0; 30

Output - Element is present at index 9

In the case given above, we need to find the index of 100, beginning with 6 from the random no. generator. We notice that arr[6] < 100 so we need to consider indices greater than 6.

Indices present next 3,5,1 are ignored.

We go to 7 next, we again see that 100>arr[7], need to search for indices greater than 7 now.

Next coming to 9, we see 100 = arr[9]. we found out a number at index 9.

There were a total of 3 comparisons.

The thing implemented in the code is the better and optimal way of generating random nos in the relevant range.