Buenas! Es mi segundo post y he vuelto a poner que mis cerebros son 1, en lugar de uno. Vaya llegada.
Me llamo Diego, 29 años y de Alicante, siempre me ha gustado la informática y en concreto programar/resolver problemas, estoy acabando ingeniería informática, así que aquí estoy por recomendación de un amigo :D
Me interesan mucho las bases de datos, la eficiencia en algoritmia y la inteligencia artificial. No os voy a aburrir con las cosas que he hecho o hago, ya iré hablando por el foro. Un saludo!

Buenas! Veo que EX3 te ha sugerido el suffle, algo así venía yo a aportar. Pero más que venir a decirte por decirte, me gustaría ayudarte a entender porqué dos blucles anidados completos en función de la longitud de tu array es una terrible solución de búsqueda.
Para un vector con menos de cientos de miles de elementos puede ser una solución decente, pues requiere poca complejidad algorítmica, lo programas en un pispás y funciona bien.
Ahora bien, cuando se te dispara la longitud debes ser consciente de la eficacia y la carga temporal de tu solución, tras cada elemento, recorrer el vector entero en una búsqueda puede ser desastroso, o puede ser magnífico; no siempre van a salirte esas cargas temporales de media o una hora, pues será en función de la semilla de los elementos random.

Por qué? Piensa que cuando vas a añadir un elemento primero lo buscas, en el mejor de los casos nunca está, esto quiere decir que por cada nuevo elemento, recorrerás tu vector una vez.
Complejidad temporal de n*log(n), muy buena.

En el peor de los casos, puede repetirse indefinidas veces el recorrido en el vector, pues no solamente sí esté el elemento si no que además está a la cola. Esto podría darte incluso un abrazo mortal en el proceso, por no llegar al final, precisamente por ser random puede que siempre estén contenidos en el vector los nuevos números.

Ahora bien, como recomendación, sin entrar en la tremenda carga que tiene la creación de números aleatorios y que no es algo que se deba usar a la ligera y menos con rangos altos de números, siempre que quieras hacer búsquedas y puedas ordenar, ordena; en este caso con números enteros, puedes ordenas y deberías, los algoritmos de ordenación y de búsqueda ordenada están más que optimizados y estudiados dándote una capacidad enorme de desarrollo sin preocuparte de la carga temporal.

Te recomiendo mirar, en búsqueda la Búsqueda Dicotómica. Que lo que hace es dividirte el vector en mitades hasta encontrar el elemento, en un vector ordenado claro.

Y te recomiendo mirar, en ordenación, QuickSort, no es difícil de implementar pero sí laborioso, ahora bien, funciona brutalmente bien.

Te voy a dejar un gif sobre carga temporal de algoritmos de ordenación:


Y por último, si no te has cansado aún de leerme, experiencia personal en una prueba que hice el año pasado:
- BubbleSort 100k elements: 38 min
- QuickSort 100k elements: 0.002 secs

Un saludo!