¿Cuántas veces es más rápida la búsqueda binaria que la búsqueda secuencial cuando se busca el elemento 592 en una lista de 1024 elementos?

Usé la sintaxis de Swift (aproximadamente) para describir mi respuesta a continuación …

var num = 1024
num / 2/2/2/2/2/2/2/2/2 = 2
Esta es la forma binaria. Sigue dividiendo por la mitad y eliminando la mitad en la que no está el número objetivo. Si lo hace, le tomará 9 conjeturas para encontrar el número 592. El máximo que obtendrá es 10.

Si lo haces de forma secuencial, vas
var num = 1 + 1 + 1 + 1 … en cada punto, verificando si el resultado es igual a tu objetivo.

Entonces su respuesta es 592 secuencialmente y 9 usando búsqueda binaria. Para saber cuántas veces más rápido es, divide 9 en 592, lo que equivale a 65.7777777777778. Entonces diría que es aproximadamente 66 veces más rápido.

Podría estar equivocado, pero así es como lo entiendo. Por cierto, hay un gran curso sobre Algoritmos en la academia Khan, lo que explica esto mucho mejor que yo.

Me gustaría agregar la función que escribí para hacer esto …

func doSearch (arr: [Int], targetValue: Int) -> Int {
var min = 0
var max = recuento de arr. – 1
var guess: Int
var numGuesses = 0
while (max> = min)
{
adivinar = Int ((min + max) / 2)
if (arr [guess] == targetValue) {
numGuesses ++
volver adivina
}
if (arr [adivinar] numGuesses ++
min = adivinar + 1
} más {
numGuesses ++
max = adivinar – 1
}
println (“Número total de conjeturas = \ (numGuesses)”)
}
volver -1
}

var arr1: [Int] = []
para (var i = 0; i <1024; i ++) {
arr1.append (i)
}
var res1 = doSearch (arr1, 592)
var num = 1024
num / 2/2/2/2/2/2/2/2/2 // <- Aquí obtengo 2

var num2 = 592.0 / 9 // <- aquí es donde obtengo 65.7777777777778
// si hiciste 592.0 / 10 porque 10 es el máximo de intentos que obtendrías 59.2

El resultado que obtengo en la consola es esto debido a las declaraciones println ():
/////////////////////
Número total de conjeturas = 1
Número total de conjeturas = 2
Número total de conjeturas = 3
Número total de conjeturas = 4
Número total de conjeturas = 5
Número total de conjeturas = 6
Número total de conjeturas = 7
Número total de conjeturas = 8
Número total de conjeturas = 9

Si se trata de una lista (vinculada), debe pasar la mitad de los elementos para el primer paso y 1/4 para el segundo, etc. Al final tendrías que revisarlos todos, lo cual es peor que la búsqueda lineal.

¿O quisiste decir vector?

1: 512-1024 (512)
2: 512-768 (256)
3: 512-640 (128)
4: 576-640 (64)
5: 576-608 (32)
6: 592! (dieciséis)
Cuando sigues sus pasos, descubres que solo son 6 iteraciones para encontrar el objetivo. Tienes suerte; eleva su límite inferior a 512 en el primer paso, luego a 576 en el cuarto, lo que significa que cuando intenta agregar 16 a 576 en el paso 6, termina girando en 592, lo que significa que tropieza con lo que estaba buscando .