¿Cómo utilizar la búsqueda binaria en un arreglo rotado?
La búsqueda binaria es una técnica esencial para buscar elementos en listas ordenadas, ya que es extremadamente eficiente con una complejidad de tiempo de O(log N). No obstante, al enfrentarnos a arreglos rotados, es crucial identificar ciertas situaciones para asegurar el éxito de nuestra búsqueda. Este conocimiento es vital tanto para el desarrollo de software como para optimizar búsquedas en grandes conjuntos de datos, y puede resultar en tiempos de ejecución considerablemente más rápidos.
¿Por qué es importante entender el concepto de arreglos rotados?
Un arreglo rotado es aquel que ha sido "girado" en un sentido, de modo que, aunque el orden original era ascendente, ahora ese orden parece alterado. Por ejemplo, el arreglo [5, 6, 7, 0, 1, 2] está rotado, y esta rotación puede ocurrir hacia la izquierda, derecha o incluso no existir. Identificar esta rotación es esencial, ya que impacta directamente en cómo debemos aplicar la búsqueda binaria.
¿Cuáles son los casos a considerar en un arreglo rotado?
Existen múltiples casos a evaluar cuando se trata de buscar en arreglos rotados:
Estado del arreglo:
Rotado: El punto medio actual podría pertenecer a una porción que incluye la rotación.
No rotado: La mitad está en un segmento donde el orden lineal original se mantiene.
Comparación con el objetivo:
Si el número deseado es menor o mayor que el valor en el punto medio, influirá en la dirección de la próxima búsqueda.
Estos casos se manejan de manera similar en esencia. Lo crucial es modificar la comparación según el estado del arreglo.
¿Cómo afecta la rotación a la decisión de búsqueda?
La presencia de rotación cambia la lógica usual de búsqueda binaria. En un segmento rotado (e.g., [7, 0]), identificar si el lado izquierdo es efectivamente menor o mayor puede ser confuso, pero este problema se resuelve ajustando las condiciones del algoritmo. Por ejemplo:
Si el lado derecho aparenta ser el menor en vez del izquierdo, simplemente redirigimos la búsqueda hacia el lado opuesto.
Implementación de la búsqueda binaria en un arreglo rotado
Veamos cómo podría implementarse:
defbuscar_elemento_rotado(arr, objetivo): izquierda, derecha =0,len(arr)-1while izquierda <= derecha: mitad =(izquierda + derecha)//2# Si encontramos el objetivoif arr[mitad]== objetivo:return mitad
# Verificamos si la mitad izquierda está ordenadaif arr[izquierda]<= arr[mitad]:if arr[izquierda]<= objetivo < arr[mitad]: derecha = mitad -1else: izquierda = mitad +1else:if arr[mitad]< objetivo <= arr[derecha]: izquierda = mitad +1else: derecha = mitad -1# Si no encontramos el objetivoreturn-1# Ejemplo de uso# Suponiendo un arreglo rotado: [5, 6, 7, 0, 1, 2]resultado = buscar_elemento_rotado([5,6,7,0,1,2],0)print("El índice del objetivo es:", resultado)# Debería imprimir "El índice del objetivo es: 3"
¿Por qué es más eficiente que otros métodos?
La búsqueda binaria en un orden rotado a menudo resulta más eficaz que una búsqueda lineal simple (O(N)), especialmente en listas grandes. Esto se debe a que, en vez de revisar cada elemento uno por uno, la búsqueda binaria divide el problema y reduce continuamente el espacio de búsqueda, ahorrando tiempo significativamente.
Este enfoque demuestra cómo un entendimiento profundo de las estructuras de datos y algoritmos puede mejorar sustancialmente la eficiencia de los programas y resalta la importancia de un conocimiento completo sobre el funcionamiento interno de técnicas fundamentales como la búsqueda binaria. ¡Sigue aprendiendo y enfrentando nuevos desafíos para afianzar estos conceptos!
¿Cómo utilizar la búsqueda binaria en un arreglo rotado?
La búsqueda binaria es una técnica esencial para buscar elementos en listas ordenadas, ya que es extremadamente eficiente con una complejidad de tiempo de O(log N). No obstante, al enfrentarnos a arreglos rotados, es crucial identificar ciertas situaciones para asegurar el éxito de nuestra búsqueda. Este conocimiento es vital tanto para el desarrollo de software como para optimizar búsquedas en grandes conjuntos de datos, y puede resultar en tiempos de ejecución considerablemente más rápidos.
¿Por qué es importante entender el concepto de arreglos rotados?
Un arreglo rotado es aquel que ha sido "girado" en un sentido, de modo que, aunque el orden original era ascendente, ahora ese orden parece alterado. Por ejemplo, el arreglo [5, 6, 7, 0, 1, 2] está rotado, y esta rotación puede ocurrir hacia la izquierda, derecha o incluso no existir. Identificar esta rotación es esencial, ya que impacta directamente en cómo debemos aplicar la búsqueda binaria.
¿Cuáles son los casos a considerar en un arreglo rotado?
Existen múltiples casos a evaluar cuando se trata de buscar en arreglos rotados:
Estado del arreglo:
Rotado: El punto medio actual podría pertenecer a una porción que incluye la rotación.
No rotado: La mitad está en un segmento donde el orden lineal original se mantiene.
Comparación con el objetivo:
Si el número deseado es menor o mayor que el valor en el punto medio, influirá en la dirección de la próxima búsqueda.
Estos casos se manejan de manera similar en esencia. Lo crucial es modificar la comparación según el estado del arreglo.
¿Cómo afecta la rotación a la decisión de búsqueda?
La presencia de rotación cambia la lógica usual de búsqueda binaria. En un segmento rotado (e.g., [7, 0]), identificar si el lado izquierdo es efectivamente menor o mayor puede ser confuso, pero este problema se resuelve ajustando las condiciones del algoritmo. Por ejemplo:
Si el lado derecho aparenta ser el menor en vez del izquierdo, simplemente redirigimos la búsqueda hacia el lado opuesto.
Implementación de la búsqueda binaria en un arreglo rotado
Veamos cómo podría implementarse:
def buscar_elemento_rotado(arr, objetivo):
izquierda, derecha = 0, len(arr) - 1
while izquierda <= derecha:
mitad = (izquierda + derecha) // 2
# Si encontramos el objetivo
if arr[mitad] == objetivo:
return mitad
# Verificamos si la mitad izquierda está ordenada
if arr[izquierda] <= arr[mitad]:
if arr[izquierda] <= objetivo < arr[mitad]:
derecha = mitad - 1
else:
izquierda = mitad + 1
else:
if arr[mitad] < objetivo <= arr[derecha]:
izquierda = mitad + 1
else:
derecha = mitad - 1
# Si no encontramos el objetivo
return -1
# Ejemplo de uso
# Suponiendo un arreglo rotado: [5, 6, 7, 0, 1, 2]
resultado = buscar_elemento_rotado([5, 6, 7, 0, 1, 2], 0)
print("El índice del objetivo es:", resultado) # Debería imprimir "El índice del objetivo es: 3"
¿Por qué es más eficiente que otros métodos?
La búsqueda binaria en un orden rotado a menudo resulta más eficaz que una búsqueda lineal simple (O(N)), especialmente en listas grandes. Esto se debe a que, en vez de revisar cada elemento uno por uno, la búsqueda binaria divide el problema y reduce continuamente el espacio de búsqueda, ahorrando tiempo significativamente.
Este enfoque demuestra cómo un entendimiento profundo de las estructuras de datos y algoritmos puede mejorar sustancialmente la eficiencia de los programas y resalta la importancia de un conocimiento completo sobre el funcionamiento interno de técnicas fundamentales como la búsqueda binaria. ¡Sigue aprendiendo y enfrentando nuevos desafíos para afianzar estos conceptos!
public static int rotatedSearch(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
// Identify which side is sorted
if (nums[left] <= nums[mid]) {// Left side is sorted
if (target >= nums[left] && target < nums[mid]) right = mid - 1;
else left = mid + 1;
}
else { // Right side is sorted
if (target > nums[mid] && target <= nums[right]) left = mid + 1;
else right = mid - 1;
}
}
return -1;
}
public static int rotatedSearch(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) return mid; // Identify which side is sorted if (nums[left] <= nums[mid]) {// Left side is sorted if (target >= nums[left] && target < nums[mid]) right = mid - 1; else left = mid + 1; } else { // Right side is sorted if (target > nums[mid] && target <= nums[right]) left = mid + 1; else right = mid - 1; } } return -1;}
Yo lo que hice fue rotar todos mis punteros (low, high, mid) una distancia k. Y luego hice un binary search normal con los apuntadores rotados y funciona.
nums = [40, 56, 62, 74, 0, 2, 5, 8]
def shifted_binary_search(l, k, target):
low = 0
high = len(l) - 1
while low <= high:
mid = (low + high) // 2
mid_mod = mid + k
high_mod = high + k
low_mod = low + k
if mid_mod >= len(l):
mid_mod = mid_mod - len(l)
if low_mod >= len(l):
low_mod = low_mod - len(l)
if high_mod >= len(l):
high_mod = high_mod - len(l)
if l[mid_mod] == target:
return mid_mod
if l[high_mod] == target:
return high_mod
if l[low_mod] == target:
return low_mod
if target < l[mid_mod]:
high = mid - 1
else:
low = mid + 1
return -1
print(shifted_binary_search(nums, 4, 74))
Aplicando la parte de que no solo busque de a 1 si no de a 3, respetando la O(long n), aunque me complique con el caso de cuando el valor no esta en la lista, pues me daba index error.
publicstatic int rotatedSearch(int[] nums, int target){ int left =0, right = nums.length-1;while(left <= right){ int mid = left +(right - left)/2;if(nums[mid]== target)return mid;// Identify which side is sortedif(nums[left]<= nums[mid]){// Left side is sortedif(target >= nums[left]&& target < nums[mid]) right = mid -1;else left = mid +1;}else{// Right side is sortedif(target > nums[mid]&& target <= nums[right]) left = mid +1;else right = mid -1;}}return-1;}
publicstatic int rotatedSearch(int[] nums, int target){ int left =0, right = nums.length-1;while(left <= right){ int mid = left +(right - left)/2;if(nums[mid]== target)return mid;// Identify which side is sorted if (nums[left] <= nums[mid]) {// Left side is sorted if (target >= nums[left] && target < nums[mid]) right = mid - 1; else left = mid + 1; } else { // Right side is sorted if (target > nums[mid] && target <= nums[right]) left = mid + 1; else right = mid - 1; } } return -1;}
Mi aporte en C++:
#include<iostream>#include<vector>int binary_search(conststd::vector<int>&arr, int tgt){//for rotated input arrays, we should extend the binary search//to find the pivot first. int left =0; int right = arr.size()-1; int mid; int pivot =0;//check if rotatedif(arr[left]> arr[right]){while(left <= right){ mid =(right + left)/2;if(arr[mid]> arr[right]){ left = mid +1;}else{ right = mid -1;}} pivot = mid;}//if there was a pivot, then i need to move either left or right pointers left =0; right = arr.size()-1;if(pivot){if(tgt > arr[left]&& tgt < arr[pivot]){ right = pivot -1;}else{ left = pivot;}}while(left <= right){ mid =(right + left)/2;if(arr[mid]== tgt){return mid;}elseif(tgt > arr[mid]){ left = mid +1;}else{ right = mid -1;}}return-1;}int main(){std::vector<int> arr ={1,5,8,11,16,23,40,56,72,99};std::cout <<"binary found: "<<binary_search(arr,11)<< std::endl; arr ={4,5,6,7,0,1,2};std::cout <<"binary found: "<<binary_search(arr,3)<< std::endl;return0;}
Aqui una solucion en scala
import scala.collection.mutable.ArrayBufferclassBinarySearchRotate{ private def reDefineIndex(  arr:Array\[Int],  index:Int,  middle:Int,  left:Int,  right:Int):(Int,Int)={ if(arr(middle)< index){ (middle, right -1) }else{ (left +1, middle) } } private def CheckIfExists(arr:Array\[Int],  left:Int,  right:Int,  search:Int):(Int,Int)={  val middle =((left + right)/2) if(arr(right)== search){ return(right,-1) } if(arr(left)== search){ return(left,-1) } if(arr(middle)== search){ return(middle,-1) } (-1, middle) }  def BinarySearch(arr:Array\[Int],search:Int):Int={ if(arr.length==0){ return-1 } var left =0 var right = arr.length-1 while(right!= left){ val(index, middle)=CheckIfExists(arr, left, right, search) if(middle ==-1){ return index
 } val(newLeft, newRight)=reDefineIndex(arr, search, middle, left, right)  right = newRight
  left = newLeft
 } 0 }}classRotateArray{  def rotateArray(array:Array\[Int],rotate:Int):Array\[Int]={  val buffer =ArrayBuffer(array: \_\*) for(i <-0 until rotate){  val item =buffer(0)  buffer.remove(0)  buffer += item
 }  buffer.toArray }}object SolutionRotated{  val *example*=Array(1,2,3,4,5,6,7)  val *targetToRotate*=3  def main(args:Array\[String]):Unit={  val bs =newBinarySearchRotate()  val index = bs.BinarySearch(*example*,*targetToRotate*)  val rt =newRotateArray()  val rotate = rt.rotateArray(*example*, index) *println*(s"data ${rotate.mkString(",")}") }}
Yo lo que hice fue rotar todos mis punteros (low, high, mid) una distancia k. Y luego hice un binary search normal con los apuntadores rotados y funciona.
nums =[40,56,62,74,0,2,5,8]defshifted_binary_search(l, k, target): low =0 high =len(l)-1while low <= high: mid =(low + high)//2 mid_mod = mid + k
high_mod = high + k
low_mod = low + k
if mid_mod >=len(l): mid_mod = mid_mod -len(l)if low_mod >=len(l): low_mod = low_mod -len(l)if high_mod >=len(l): high_mod = high_mod -len(l)if l[mid_mod]== target:return mid_mod
if l[high_mod]== target:return high_mod
if l[low_mod]== target:return low_mod
if target < l[mid_mod]: high = mid -1else: low = mid +1return-1print(shifted_binary_search(nums,4,74))
Aplicando la parte de que no solo busque de a 1 si no de a 3, respetando la O(long n), aunque me complique con el caso de cuando el valor no esta en la lista, pues me daba index error.
