Busqueda binaria La búsqueda binaria sólo se puede implementar si el arreglo está ordenado. La idea consiste en ir dividiendo el arreglo en mitades. Por ejemplo supongamos que tenemos este vector:int vector[10] = {2,4,6,8,10,12,14,16,18,20};La clave que queremos buscar es 6. El algoritmo funciona de la siguien maneraSe determinan un indice arriba y un indice abajo, Iarriba=0 e Iabajo=9 respectivamente. Se determina un indice central, Icentro = (Iarriba + Iabajo)/2, en este caso quedaría Icentro = 4. Evaluamos si vector[Icentro] es igual a la clave de busqueda, si es igual ya encontramos la clave y devolvemos Icentro. Si son distintos, evaluamos si vector[Icentro] es mayor o menos que la clave, como el arreglo está ordenado al hacer esto ya podemos descartar una mitad del arreglo asegurandonos que en esa mitad no está la clave que buscamos. En nuestro caso vector[Icentro] = 4 < 6, entonces la parte del arreglo vector[0...4] ya puede descartarse. Reasignamos Iarriba o Iabajo para obtener la nueva parte del arreglo en donde queremos buscar. Iarriba, queda igual ya que sigue siendo el tope. Iabajo lo tenemos subir hasta 5, entonces quedaria Iarriba = 9, Iabajo = 5. Y volvemos al paso 2. Si la clave no fuese encontrada en algun momento Iabajo > Iarriba, con un while vamos a controlar esta condición para salir del ciclo en tal caso y devolver -1 (clave no encontrada).

int busquedaBinaria(const int arreglo[], int tamano, int clave){  int Iarriba = tamano-1;  int Iabajo = 0;  int Icentro;  while (Iabajo <= Iarriba)    {      Icentro = (Iarriba + Iabajo)/2;      if (arreglo[Icentro] == clave) return Icentro;      else if (clave < arreglo[Icentro])   Iarriba=Icentro-1; else   Iabajo=Icentro+1;    }  return -1;}

QuicksortComo se puede suponer, la eficiencia del algoritmo depende de la posición en la que termine el pivote elegido.En el mejor caso, el pivote termina en el centro de la lista, dividiéndola en dos sublistas de igual tamaño. En este caso, el orden de complejidad del algoritmo es O(n·log n). En el peor caso, el pivote termina en un extremo de la lista. El orden de complejidad del algoritmo es entonces de O(n²). El peor caso dependerá de la implementación del algoritmo, aunque habitualmente ocurre en listas que se encuentran ordenadas, o casi ordenadas. En el caso promedio, el orden es O(n·log n). Demostración [editar]Vamos a suponer que el número total de elementos a ordenar es potencia de dos, es decir, n = 2k. de Aquí podemos ver que k = log2(n), donde k es el número de divisiones que realizará el algoritmo.En la primera fase del algoritmo habrán n comparaciones, en la segunda fase el algoritmo creará dos sublistas aproximadamente de tamaño n/2. El número total de comparaciones de estas dos sublistas es: 2(n/2) = n. En la tercera fase el algoritmo procesará 4 sublistas más, por tanto el número total de comparaciones en esta fase es 4(n/4) = n.En conclusión, el número total de comparaciones que hace el algoritmo es:n + n + n + ..... + n = kn, donde k = log2(n), por tanto la complejidad es O(n.log2n)