Introducción

1

Arrays y Strings para resolver algoritmos avanzados

2

Arrays y Strings en detalle

Dos Apuntadores

3

Patrón de Dos Apuntadores

4

Verifying Alien Dictionary: análisis del problema

5

Solución de Verifying Alien Dictionary

6

Playground: Verifying Alien Dictionary

7

Programando Verifying Alien Dictionary con JavaScript

8

Merge Two Sorted Lists: análisis del problema

9

Solución de Merge Two Sorted Lists

10

Playground: Merge Two Sorted Lists

11

Programando Merge Two Sorted Lists con Python

12

Container With Most Water: análisis del problema

13

Solución de Container With Most Water

14

Playground: Container with Most Water

15

Programando Container With Most Water con Java

16

Reto: Trapping Rain Water

17

Ejercicios recomendados de Dos Apuntadores

18

Ejercicios resueltos de Dos Apuntadores

Ventana Deslizante

19

Patrón de Ventana Deslizante

20

Longest Substring Without Repeating Characters: análisis del problema

21

Solución de Longest Substring Without Repeating Characters

22

Playground: Longest Substring Without Repeating Characters

23

Programando Longest Substring Without Repeating Characters con Python

24

Ejercicios recomendados de Ventana Deslizante

25

Ejercicios resueltos de Ventana Deslizante

Búsqueda Binaria

26

Algoritmo de Búsqueda Binaria

27

Search in Rotated Arrays: análisis del problema

28

Solución de Search in Rotated Arrays

29

Playground: Search in Rotated Arrays

30

Programando Search in Rotated Arrays

31

Search 2D Array Matrix: análisis del problema

32

Solución de Search 2D Array Matrix

33

Playground: Search 2D Array Matrix

34

Programando Search 2D Array Matrix

Próximos pasos

35

Toma el Curso Avanzado de Algoritmos: Estructuras de Datos Lineales

No tienes acceso a esta clase

¡Continúa aprendiendo! Únete y comienza a potenciar tu carrera

Solución de Search in Rotated Arrays

28/35
Recursos

Aportes 4

Preguntas 0

Ordenar por:

¿Quieres ver más aportes, preguntas y respuestas de la comunidad?

Aqui una solucion en scala ``` import scala.collection.mutable.ArrayBuffer class BinarySearchRotate { 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 } } class RotateArray { 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 = new BinarySearchRotate() val index = bs.BinarySearch(*example*, *targetToRotate*) val rt = new RotateArray() val rotate = rt.rotateArray(*example*, index) *println*(s"data ${rotate.mkString(",")}") } } ```
```js function searchBinary(){ let s = [1,5,8,11,16,23,40,56,72,99]; let p1 = 0; let p2 = s.length - 1; let target = 0; while(p1 <= p2){ let mid = Math.floor(p1 + (p2 - p1) / 2); if(s[mid] === target){ return mid }else if(s[mid] < target){ return mid + 1 }else{ p2 = mid - 1 } p1++ } return -1 } searchBinary(); ```
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. ```python 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.