Galloping search is a similar algorithm to binary search. Using the pseudocode below, implement and test a function that takes a sorted list and a value as input and performs a galloping search. In general, binary search performs better than galloping. Can you think of cases where galloping search would be faster?

GallopingSearch(list, searchvalue):

1. Set start to 0 and end to 1 2. While end < length of list and the value at index end in the list < search value:

2a. Set start to end

2b. Multiply end by 2 3. Use another search (e.g., linear, binary) to look between the final start/end values

Note: You can modify the binary search function from the lecture to accept start/end value inputs (instead of initializing them to 0 and len(list)-1) and use that function to search between the start/end values identified by galloping search.

USE PYTHON