In binary search, you repeatedly divide the sorted array in half to search for a specific key efficiently. Here's the sequence of keys that would be compared with the search key 89 in the given sorted array:
1. Start with the whole array:
- Array: [20, 30, 38, 47, 48, 49, 51, 67, 73, 75, 78, 84, 89, 92, 98]
2. First comparison:
- Middle element: 51
- Since 89 is greater than 51, we eliminate the left half of the array.
3. Second comparison:
- Middle element: 78
- Since 89 is greater than 78, we eliminate the left half again.
4. Third comparison:
- Middle element: 92
- Since 89 is less than 92, we eliminate the right half.
5. Fourth comparison:
- Middle element: 84
- Since 89 is greater than 84, we eliminate the left half again.
6. Fifth comparison:
- Middle element: 89
- We have found the search key 89 in the array.
So, the sequence of keys compared while binary searching for 89 is: 51, 78, 92, 84, 89.