0-based
Python is a 0-based language. A sequence of length n has elements running from index 0 to n-1. There is no need to write high = len(arr) - 1 and then test using <= to include the end of the range. Simply drop the - 1 (and the cost of the unnecessary subtraction calculation) and test with <.
low = 0
high = len(arr) # no "- 1" here
while low < high: # use "<" here
mid = (high + low) // 2
if arr[mid] == x:
return mid
elif arr[mid] < x:
low = mid + 1
else:
high = mid # no "- 1" here
Repeated indexing
You fetch arr[mid] twice in your search loop. Indexing into a random-access array shouldn't be expensive, but why pay any extra cost? Cache the looked up value.
val = arr[mid]
if val == x:
return mid
elif val < x:
...
Reworked code
Using some of the suggestions by J_H and Reinderien, (although we still reinvent-the-wheel, since the requirement is to write the search function) we can rework the code as follows:
FICTIONAL = 9_999
NOT_FOUND = -1
def smart_search(arr: list[int], x: int) -> int:
"""
Find 'x' in sorted list of integers, in O(log m) time.
'arr' contains a 'm' actual values, and 'n-m' padding values.
Returns:
if present: index of 'x'
otherwise: NOT_FOUND (-1)
"""
# Fast fail
if x >= FICTIONAL:
return NOT_FOUND
n = len(arr)
if n == 0:
return NOT_FOUND
# Telescoping estimate of 'm'
m_est = 1
while m_est < n and arr[m_est] != FICTIONAL:
m_est *= 2
m_est = min(m_est, n)
# Standard binary search
low = 0
high = m_est
while low < high:
mid = (low + high) // 2
val = arr[mid]
if val == x:
return mid
elif val < x:
low = mid + 1
else:
high = mid
return NOT_FOUND
Testing
Let's mock an array with the sequence 0, 10, 20, ...
and count the number of times we index into the array.
class MockArray:
"""
A mock array of length 'n'.
The 'array' contains 'm' ascending values, followed by 'n-m'
fictitious values representing unused entries.
Accesses to the array are counted, for instrumentation.
'm' is not returned by any public method.
"""
def __init__(self, n: int, m: int):
self._n = n
self._m = m
self._gets = 0
if not (0 <= m <= n):
raise ValueError("Invalid n and/or m")
if m >= 1000:
raise ValueError("m is too big")
def __len__(self) -> int:
return self._n
def __getitem__(self, index: int) -> int:
if index < 0:
index += self._n
if index < 0 or index >= self._n:
raise IndexError()
self._gets += 1
if index < self._m:
return index * 10 # Fake storage of ascending data
else:
return FICTIONAL # Fake storage of fictional data
def num_gets(self):
return self._gets
Then we can add a small test scaffold ...
def _test_smart_search(n: int, m: int, x: int, expected: int, limit: int):
arr = MockArray(n, m)
index = smart_search(arr, x)
assert index == expected, f"{m=}: expected {expected}, got {index}"
assert arr.num_gets() <= limit, f"{arr.num_gets()} > {limit}"
... which creates the mock array, searches for the given element, and validates if the correct result was returned and no more than the given number of array lookups were made, to validate the time O-requirement.
Finally, we can use this to run a number of tests on a billion element array.
def test_smart_search():
for m in range(1000):
limit = m.bit_length() * 2 + 2
target = 50
expected = target // 10 if m*10 > target else NOT_FOUND
_test_smart_search(1_000_000_000, m, target, expected, limit)
if __name__ == '__main__':
test_smart_search()
highas follows:while high >= 0 and arr[high] == 999: high -= 1. But what if you had an array of 200 elements of which the last 100 have the value9999. You would be looping 100 times to sethighfrom its initial value of 199 to 99. If you did nothing you would computemidinitially to be 99. Ifarr[99]is less than thexvalue you seek you will discover on your next iteration that the value does not exist. Otherwise you have eliminated the 100 fictitious numbers with one search. So do nothing. \$\endgroup\$smartSearch([1,88888,88889,9999,9999], 88888):\$\endgroup\$