Question

1. Write a recursive method that performs binary search on an array Arr and searches for a key k.

Apply the recursive method to the following array: 13 | 20 | 22 | 26 | 30 | 41 | 50 | 60

While the key you are search for is 50.

Show the stack trace.

Answer 1

/*If you have any query do comment in the comment section else like the solution*/

int findKey(int arr[], int key, int low, int high) {
        if (high >= low) { 
                int mid = (low + high)/2; 
                if (arr[mid] == key) return mid; 
                if (arr[mid] > key) {      
          return findKey(arr, key, low, mid-1); 
        }               
                return findKey(arr, key, mid+1, high); 
        }
        return -1; 
}

Stack Trace:

findKey(arr, 50, 0, 7)
findKey(arr, 50, 4, 7)
findKey(arr, 50, 6, 7)