Develop an implementation BinarySearchST of the symbol-table API that maintains parallel arrays of keys and values, keeping them in key-sorted order. Use binary search for get, and move larger key-value pairs to the right one position for put (use a resizing array to keep the array length proportional to the number of keyvalue pairs in the table). Test your implementation with Index, and validate the hypothesis that using such an implementation for Index takes time proportional to the product of the number of strings and the number of distinct strings in the input.