An unsorted list of integers allows for constant-time insert simply by adding a new integer at the end of the list. Unfortunately, searching for the integer with key value X requires a sequential...

An unsorted list of integers allows for constant-time insert simply by adding a new integer at the end of the list. Unfortunately, searching for the integer with key value X requires a sequential search through the unsorted list until you find X, which on average requires looking at half the list. On the other hand, a sorted array-based list of n integers can be searched in log n time by using a binary search. Unfortunately, inserting a new integer requires a lot of time because many integers might be shifted in the array if we want to keep it sorted. How might data be organized to support both insertion and search in log n time?