Playground: Search in Rotated Arrays

Clase 29 de 35 • Curso de Algoritmos Avanzados: Patrones de Arrays y Strings

Contenido del curso

Introducción

Dos Apuntadores

Ventana Deslizante

Búsqueda Binaria

Próximos pasos

35
Estructuras de Datos Lineales: Conceptos y Aplicaciones
00:36 min

Tomar examen

Comentarios

Ivan Camilo Buitrago Buitrago

student•

Aca mi solucion cualquier aporte o comentario sera bien recibido: ` js export function searchInRotatedArray(nums, objetivo) { let inicio = 0; let fin = nums.length - 1;

while (inicio <= fin) { const medio = Math.floor((inicio + fin) / 2);

if (nums[medio] === objetivo) {
  return medio;
}

// Verificar en qué mitad del arreglo estamos
if (nums[inicio] <= nums[medio]) {
  // La primera mitad está ordenada
  if (nums[inicio] <= objetivo && objetivo < nums[medio]) {
    fin = medio - 1;
  } else {
    inicio = medio + 1;
  }
} else {
  // La segunda mitad está ordenada
  if (nums[medio] < objetivo && objetivo <= nums[fin]) {
    inicio = medio + 1;
  } else {
    fin = medio - 1;
  }
}

}

return -1; // Si no se encuentra el objetivo }

John Eduard Meneses González

student•

My solution:

Bryan Castano

student•

Non Spoilers \n\n\n...

//Search in Rotated Arrays num[ objetivo ] if not return -1; ....

export function searchInRotatedArray(nums, objetivo) {
  // Tu código aquí....
  
  let left = 0; 
  let right = nums.length -1 ;
  
  while ( left <= right ) {
    
    let mid =  Math.floor(  left + right) /2 ) ;
    
    if (  nums[ mid ]  == objetivo )  {
    
      return mid ; 
    
    }
      
    if (  nums[ left ] <= nums[ mid ] ) {
    
       if ( nums[ left ] <= objetivo && objetivo < nums[ mid ]  ) {
       
         right =  mid -1 ; 
         
       } else {
       
         left = left + 1 ; 
        
       }  else { 
         
         if ( nums [ mid ]  < objetivo && objetivo <= nums[ right] ) {
         
           left = mid + 1 ; 
         
         } else {
         
           right = mid -1 ; 
           
           
           }
       
       }
    
  }
  
  return -1 ; 
  
  
}

```//Search in Rotated Arrays num\[ objetivo ] if not return -1; ....



export function searchInRotatedArray(nums, objetivo) {

&#x20; // Tu código aquí....

&#x20;&#x20;

&#x20; let left = 0;&#x20;

&#x20; let right = nums.length -1 ;

&#x20;&#x20;

&#x20; while ( left <= right ) {

&#x20;  &#x20;

&#x20;   let mid =  Math.floor(  left + right) /2 ) ;

&#x20;  &#x20;

&#x20;   if (  nums\[ mid ]  == objetivo )  {

&#x20;  &#x20;

&#x20;     return mid ;&#x20;

&#x20;  &#x20;

&#x20;   }

&#x20;    &#x20;

&#x20;   if (  nums\[ left ] <= nums\[ mid ] ) {

&#x20;  &#x20;

&#x20;      if ( nums\[ left ] <= objetivo && objetivo < nums\[ mid ]  ) {

&#x20;     &#x20;

&#x20;        right =  mid -1 ;&#x20;

&#x20;       &#x20;

&#x20;      } else {

&#x20;     &#x20;

&#x20;        left = left + 1 ;&#x20;

&#x20;      &#x20;

&#x20;      }  else {&#x20;

&#x20;       &#x20;

&#x20;        if ( nums \[ mid ]  < objetivo && objetivo <= nums\[ right] ) {

&#x20;       &#x20;

&#x20;          left = mid + 1 ;&#x20;

&#x20;       &#x20;

&#x20;        } else {

&#x20;       &#x20;

&#x20;          right = mid -1 ;&#x20;

&#x20;         &#x20;

&#x20;         &#x20;

&#x20;          }

&#x20;     &#x20;

&#x20;      }

&#x20;  &#x20;

&#x20; }

&#x20;&#x20;

&#x20; return -1 ;&#x20;

&#x20;&#x20;

&#x20;&#x20;

}

Miguel Angel Reyes Moreno

student•

código:

export function searchInRotatedArray(nums, objetivo) {  if (nums.length === 1) {    return nums\[0] === objetivo ? 0 : -1;  }
&#x20; let left = 0;  let right = nums.length - 1;
&#x20; while (left <= right) {    let middle = Math.floor((left + right) / 2);    if (nums\[middle] === objetivo) {      return middle;    }
&#x20;   // Determine which half is sorted    if (nums\[left] <= nums\[middle]) {  // Left half is sorted      if (nums\[left] <= objetivo && objetivo < nums\[middle]) {        right = middle - 1;      } else {        left = middle + 1;      }    } else {  // Right half is sorted      if (nums\[middle] < objetivo && objetivo <= nums\[right]) {        left = middle + 1;      } else {        right = middle - 1;      }    }  }
&#x20; return -1;  // objetivo not found}

Nicolas Alpargatero

student•

Lo tenía en python la IA lo paso a Js

. .

Miguel Angel Reyes Moreno

student•

Jajaja buenísimo el escudo anti-spoiler

Kengya Moncada

student•

if (nums[medio] === objetivo) {
  return medio;
}

// Verificar en qué mitad del arreglo estamos
if (nums[inicio] <= nums[medio]) {
  // La primera mitad está ordenada
  if (nums[inicio] <= objetivo && objetivo < nums[medio]) {
    fin = medio - 1;
  } else {
    inicio = medio + 1;
  }
} else {
  // La segunda mitad está ordenada
  if (nums[medio] < objetivo && objetivo <= nums[fin]) {
    inicio = medio + 1;
  } else {
    fin = medio - 1;
  }
}

//Search in Rotated Arrays num[ objetivo ] if not return -1; ....

export function searchInRotatedArray(nums, objetivo) {
  // Tu código aquí....
  
  let left = 0; 
  let right = nums.length -1 ;
  
  while ( left <= right ) {
    
    let mid =  Math.floor(  left + right) /2 ) ;
    
    if (  nums[ mid ]  == objetivo )  {
    
      return mid ; 
    
    }
      
    if (  nums[ left ] <= nums[ mid ] ) {
    
       if ( nums[ left ] <= objetivo && objetivo < nums[ mid ]  ) {
       
         right =  mid -1 ; 
         
       } else {
       
         left = left + 1 ; 
        
       }  else { 
         
         if ( nums [ mid ]  < objetivo && objetivo <= nums[ right] ) {
         
           left = mid + 1 ; 
         
         } else {
         
           right = mid -1 ; 
           
           }
       
       }
    
  }
  
  return -1 ; 
  
}

```//Search in Rotated Arrays num\[ objetivo ] if not return -1; ....

export function searchInRotatedArray(nums, objetivo) {

&#x20; // Tu código aquí....

&#x20;&#x20;

&#x20; let left = 0;&#x20;

&#x20; let right = nums.length -1 ;

&#x20;&#x20;

&#x20; while ( left <= right ) {

&#x20;  &#x20;

&#x20;   let mid =  Math.floor(  left + right) /2 ) ;

&#x20;  &#x20;

&#x20;   if (  nums\[ mid ]  == objetivo )  {

&#x20;  &#x20;

&#x20;     return mid ;&#x20;

&#x20;  &#x20;

&#x20;   }

&#x20;    &#x20;

&#x20;   if (  nums\[ left ] <= nums\[ mid ] ) {

&#x20;  &#x20;

&#x20;      if ( nums\[ left ] <= objetivo && objetivo < nums\[ mid ]  ) {

&#x20;     &#x20;

&#x20;        right =  mid -1 ;&#x20;

&#x20;       &#x20;

&#x20;      } else {

&#x20;     &#x20;

&#x20;        left = left + 1 ;&#x20;

&#x20;      &#x20;

&#x20;      }  else {&#x20;

&#x20;       &#x20;

&#x20;        if ( nums \[ mid ]  < objetivo && objetivo <= nums\[ right] ) {

&#x20;       &#x20;

&#x20;          left = mid + 1 ;&#x20;

&#x20;       &#x20;

&#x20;        } else {

&#x20;       &#x20;

&#x20;          right = mid -1 ;&#x20;

&#x20;         &#x20;

&#x20;         &#x20;

&#x20;          }

&#x20;     &#x20;

&#x20;      }

&#x20;  &#x20;

&#x20; }

&#x20;&#x20;

&#x20; return -1 ;&#x20;

&#x20;&#x20;

&#x20;&#x20;

}

export function searchInRotatedArray(nums, objetivo) {  if (nums.length === 1) {    return nums\[0] === objetivo ? 0 : -1;  }
&#x20; let left = 0;  let right = nums.length - 1;
&#x20; while (left <= right) {    let middle = Math.floor((left + right) / 2);    if (nums\[middle] === objetivo) {      return middle;    }
&#x20;   // Determine which half is sorted    if (nums\[left] <= nums\[middle]) {  // Left half is sorted      if (nums\[left] <= objetivo && objetivo < nums\[middle]) {        right = middle - 1;      } else {        left = middle + 1;      }    } else {  // Right half is sorted      if (nums\[middle] < objetivo && objetivo <= nums\[right]) {        left = middle + 1;      } else {        right = middle - 1;      }    }  }
&#x20; return -1;  // objetivo not found}

Playground: Search in Rotated Arrays

Introducción

Patrones de Arreglos y Strings: Ventana Deslizante y Dos Apuntadores

Arrays y Strings: Funcionamiento y Complejidades Temporales

Dos Apuntadores

Patrón de Dos Apuntadores en Algoritmos de Lista

Verificación de Orden en Diccionario Alienígena

Ordenamiento de Palabras en Idiomas Alienígenas

Playground: Verifying Alien Dictionary

Ordenación de Palabras en Diccionario Alienígena

Combinar Listas Ordenadas en un Array Ascendente

Ordenamiento de Listas con Complejidad Óptima y Espacio Constante

Playground: Merge Two Sorted Lists

Intercalación de Listas Ordenadas en Python

Resolver el problema "Container with Most Water" en Python

Cálculo Óptimo de Área en Listas de Alturas

Playground: Container with Most Water

Implementación de solución de cálculo de área máxima en Java

Implementación de Trapping Rainwater en Complejidad Lineal

Retos de Algoritmos con Apuntadores en Python

Patrones de Dos Apuntadores: Soluciones a Problemas Comunes en Python

Ventana Deslizante

Patrón Ventana Deslizante para Análisis de Datos Secuenciales

Subcadena más larga sin caracteres repetidos: patrón ventana deslizante

Algoritmo de Ventana Deslizante para Subcadenas Únicas

Playground: Longest Substring Without Repeating Characters

Algoritmo Python para Substring más Largo Sin Repeticiones

Retos de Algoritmos: Dos Apuntadores y Subcadenas

Máximos 1s Consecutivos y Subcadenas sin Repeticiones

Búsqueda Binaria

Algoritmo de búsqueda binaria en listas ordenadas

Búsqueda en Arrays Rotados: Encontrar Entero en Lista Ordenada

Búsqueda Binaria en Arreglos Rotados

Playground: Search in Rotated Arrays

Búsqueda en Arrays Rotados con C++

Búsqueda eficiente en matriz ordenada MxN

Búsqueda Binaria en Matrices 2D Ordenadas

Playground: Search 2D Array Matrix

Búsqueda Binaria en Matrices con Python

Próximos pasos

Estructuras de Datos Lineales: Conceptos y Aplicaciones