0

Búsqueda binaria C++iterativa.

Gabriel
joga
8635

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;

}
´´´

Escribe tu comentario
+ 2
1
8635Puntos

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;
}
1
8635Puntos

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.