Write an efficient function in the Python language called SmartSearch, this function will receive a sorted arr array of integers of size \$n\$ containing at the beginning \$m\$ "significant numbers" and the rest of the numbers are "fictitious numbers" whose value is 9999. The function also receives a number \$x\$ to be searched for in the array. If the number is in the array, the function must return its index (position), if the number \$x\$ does not exist, it must return -1. Important note: the size \$m\$ is unknown. Required efficiency: \$O(\log m)\$
Write an efficient function in the Python language called SmartSearch. This function will receive a sorted
arrarray of integers of size \$n\$ containing at the beginning \$m\$ "significant numbers" and the rest of the numbers are "fictitious numbers" whose value is 9999. The function also receives a number \$x\$ to be searched for in the array. If the number is in the array, the function must return its index (position). If the number \$x\$ does not exist, it must return -1. Important note: the size \$m\$ is unknown. Required efficiency: \$O(\log m)\$
I tried that, but I don't think it quite answers the question. I would appreciate corrections please. I realized that I should first find in which index the fictitious numbers start, and then refer only to the list without the fictitious numbers. How do you do that?
def smartSearch(arr, x):
if x == 9999:
return -1
low = 0
high = len(arr) - 1
while low <= high:
mid = (high + low) // 2
if arr[mid] == x:
return mid
elif arr[mid] < x:
low = mid + 1
else:
high = mid - 1
return -1
def smartSearch(arr, x):
if x == 9999:
return -1
low = 0
high = len(arr) - 1
while low <= high:
mid = (high + low) // 2
if arr[mid] == x:
return mid
elif arr[mid] < x:
low = mid + 1
else:
high = mid - 1
return -1
