Hola, entiendo que el curso es en Python, pero quiero compartirlos una solución a la búsqueda binaria que es iterativa. En lo personal ma gusta un tanto mas, puesto que para mi es más fácil de implementar y de entender.
´´´
int binary_search(int target, vector<int>& nums) {
int left = 0;
int right = mums.size() - 1;
while(l <= r) {
int mid = left + (right - left)/2;
if(nums[mid] == target) {
return target;
} else if(nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
´´´
Una disculpa, tiene unos typos jaja
pero aqui esta mejor
int binary_search(int target, vector<int>& nums) { intleft = 0; intright = mums.size() - 1; while(l <= r) { intmid = left + (right - left)/2; if(nums[mid] == target) { return target; } elseif(nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1; }
Y aquí está en Python 😃
defbinary_search(arr, x): low = 0 high = len(arr) - 1 mid = 0while low <= high: mid = left + (high - low) // 2if arr[mid] < x: low = mid + 1elif arr[mid] > x: high = mid - 1else: return mid return-1
Fijense como la formula de mid es left + (high - low)//2, esto con el fin de evitar posibles overflows.