SSTable Binary Search Steps

Problem

Count the comparisons binary search needs on a sorted SSTable index.

sorted_keys is the sorted index key list and target is the lookup key. Simulate the standard halving loop and count each comparison.

Return [comparisons, index]; the index is -1 when the key is absent.

Hint

Count a comparison even when the probe misses.

case 1

in: [[1,3,5,7,9],5]

expected: [1,2]

case 2

in: [[1,3,5,7],4]

expected: [2,-1]

case 3

in: [[],1]

expected: [0,-1]

case 4

in: [[7],7]

expected: [1,0]

Starter codePython

def sstable_search_steps(sorted_keys, target):
    # Your code here
    pass

4 test cases · run your code against them in the editor