Algoritmos de búsqueda

Clase 39 de 39 • Curso de Algoritmos con C 2017

Clase anteriorSiguiente clase

Edwin Balseca García

student•

Un breve resumen de todo lo visto en el curso:

Un algoritmo es una serie de pasos definidos y logicos que solucionan una tarea especifica acerca de un problema.
Tipos de algoritmos segun su funcion: ordenamiento, busqueda y encaminamiento.
Tipos de algoritmos segun el sistema de signos: cualitativos y cuantitativos.
Algoritmos computacionales: pseudocodigo, lenguajes de programacion y lenguaje natural.
Caracteristicas de los algoritmos:
-Orden definido.
-Debe respetar el orden inicial.
-Mismo resultado siempre.
-Finito.
El lenguaje ensamblador lo proporciona el fabricante del microcontrolador.
Entre más bajo se el nivel de un lenguaje de programación, más directo va a ser para trabajar con el Hardware.
Tipos de datos: numericos, logicos y alfanumericos.
Tipos de datos abstractos: tipo de datos definido por el usuario con un operador que se va a utilizar en aplicaciones.
Estructuras de datos: listas, arreglos, listas ordenadas, arboles, etc.
Metodologia para contruir un algoritmo:
-Definición del problema.
-Análisis del problema.
-Diseño del algoritmo.
-Verificación o pruebas.
Para hacer un análisis del ritmo de crecimiento, siempre vamos a tomar el término de mayor peso.
Tipos de estructuras de control: secuenciales, selectivas y repetitivas.
Dennis Ritchie: creador del lenguaje C en 1972. laboratorios bell.
Un estándar en C significa una serie de guías y directivas que se deben de seguir al momento de escribir tu código que están respaldadas por una asociación (ANSI).
C es un lenguaje de programación compilado.
C es un lenguaje tipado.
Caracteristicas importantes:
-Núcleo del lenguaje simple que opera con bibliotecas.
-Acceso a memoria de bajo nivel con punteros.
-Utiliza un conjunto reducido de palabras clave.
-Pasaje de parámetros por valor y referencia.
Tipos de errores en C: sintacticos, de el enlace, de ejecucion y semanticos.
Reglas para los identificadores:
-Longitud ilimitada, pero se recomienda usar nombres descriptivos pero cortos.
-Deben comenzar con una letra o guión bajo.
-No se puede usar números.
-No se puede usar caracteres especiales.
-Deben ser únicos en el programa.
-Énfasis en la diferencia entre mayúsculas y minúsculas.
-No puede coincidir con una palabra reservada del lenguaje o con una función de biblioteca.
Tipos de operadores en C: asignacion, relacionales, aritmeticos y logicos.
En el lenguaje de programación de C no existen los valores booleanos, por lo que así se definen:
-Valor verdadero. Cualquier número que sea distinto a cero.
-Valor falso. Cero.
Codigos de formato del lenguaje C:
-%d. Enteros.
-%c. Caracter.
-%x. Entero hexadecimal.
-%f. Numero real.
-%s. Cadena de caracteres.
-%X.Yf. Numero real con X cifras enteras y Y cifras decimales.
Forma de declarar un arreglo de caracteres: char userName[25]; y para guardarlo utilizamos scanf("%s", userName);.
La funcion strcmp pertenece a la libreria string y compara dos cadenas de caracteres, devuelve 0 si son iguales.

Jecsham Castillo

student•

Buen resumen

Juan Sarmiento A.

student•

Buen aporte

Danelia Sanchez Sanchez

student•

Búsqueda binaria:

#include <stdio.h>

int binarySearch(int array[], int n, int x)
{
  int min, max, p;
  min = 0;
  max = n;
  while(max >= min)
  {
    p = (max + min) / 2;
    if(array[p] == x)
      return p;
    else if(array[p] < x)
      min = p + 1;
    else
      max = p - 1;
  }

  return -1;
}

int main()
{
  int pos;
  int vector[] = {11, 22, 36, 47, 51, 62, 79, 85, 93, 100};
  int n = sizeof(vector) / sizeof(vector[0]);
  pos = binarySearch(vector, n, 62);
  printf("%d\n", pos);

  return 0;
}

María Alejandra Correa Rojas

student•

Hola, tengo 2 preguntas

¿Porque la funcion principal ya no la llamamos void main() sino int main()?
¿Porque cuando se imprime el valor de pos no se coloca &pos?

Diego Forero

Team Platzi•

se usa void cuando la función no retorna nada, se usa int si se espera que retorne un valor entero.

Se usa el & con scandf no con printf ya que imprimes la variable, con el scanf se usa para asignar la variable capturada por medio de la dirección de la variable.

Diego Osorio

student•

Estoy mostrando en pantalla el valor que returna sizeof(vector) y el resultado es 40, ¿Por que?

void main(){
	int vector[] = {11, 22, 36, 47, 51, 62, 79, 85, 93, 100};
	//int n = sizeof(vector) / sizeof(vector[0]);
	int n = sizeof(vector);
	printf("%i",n);
}

Diego Forero

Team Platzi•

sizeof de un vector va a regresar la suma de los tipos de cada elemento del array, en este caso como son 10 enteros * 4 que es el valor que representa el integer entonces sera 40.

Mauricio Lopez Agudelo

student•

SizeOf retorna la cantidad de bytes que ocupa tu vector en memoria, cada dato del vector ocupa 4 bytes.

Francisco Sebastian Dueñas Caicedo

student•

Gracias por el curso, aprendí muchas cosas valiosas y espero poder aplicarlas en un futuro uwu

Ricardo Celis

teacher•

Gracias a ti Leron! No olvides obtener tu diploma y todo =)

Drew Meat

student•

Algo de esta clase me huele a deja vu.

Jecsham Castillo

student•

Lineal search

#include <stdio.h>

int search(int vector_entrada[], int n, int x)
{
    int i;
    for(i = 0; i<n;i++)
    {
        if(vector_entrada[i] == x){
            return i;
        }
    }
    return -1;
}

void main()
{
    int pos;
    int n = 10;
    int vector_entrada[] = {10, 12, 13, 23, 87, 129, 20, 87, 91, 22};
    pos = search(vector_entrada, n, 20);
    printf("%d", pos);
}

Renny Galindez

student•

Presente el examen y lo aprobé! pero tengo una respuesta mal a la pregunta ¿La forma de importar librerias propias en C es?

<h1>usando los simbolos <></h1> <h1>usando los simbolos ()</h1> <h1>usando los simbolos “”</h1> <h1>usando los simbolos {}</h1>

Elegí usando los simbolos <> y me la corrigió mal, cual es la respuesta entonces? Me gustaria salir de la duda
Gracias

Antonio Madrid

student•

Para librerías que no son estándar de C, como las que podrían ser las tuyas propias se usan dobles comillas "

Ejemplos:
#include <stdio.h>
Librería de entrada y salida de C

#include "myLibrary"
importar tu propia librería

#include "angularLibrary"
importaría la biblioteca de angular, ya se que eso es de javascript, no se me ocurría una librería externa de C

Renny Galindez

student•

¡Gracias por la respuesta!

Nicolas Sanchez

student•

Me ayudan con mi codigo? Quiero buscar por ej el valor nueve y me retorna que esta en la posicion 0 ? Donde esta el error?

#include <stdio.h>

int search(int vector_entrada[], int n, int x)
{
  int i;
  for(i=0; i<n; i++)
  {
    if(vector_entrada[i])
    {
      return i;
    }
  }
  return -1;
}

int main()
{
  int pos;
  int n = 10;
  int vector_entrada[] = {1,2,3,4,5,6,7,8,9,55};
  pos = search(vector_entrada, n, 9);
  printf("%d", pos);
}```

Lucas Antognini

student•

Acá

if(vector_entrada[i])

No le estas diciendo a c que número debe buscar, y como c toma los valores verdaderos cualquier número positivo, cuando lee el 1 simplemente sale del bucle

Nicolas Sanchez

student•

Gracias por tu ayuda!!!

Esther Janeth Machado Valenzuela

student•

#include <stdio.h>

int binarySearch(int vector_entrada[], int n, int x)
{
  int p = 0;
  int r = n;

  while(p <= r){
    m = (p+r)/2
    if(vector_entrada[m] == x){
      return m;
    }
    if (vector_entrada[m] < x) {
      p = mid + 1;
    }else{
      r = mid - 1;
    }
  }
  return -1;
}

int main()
{
  int pos;
  int n = 10;
  int vector_entrada[] = {10, 25, 26, 27, 30, 50, 58, 88, 100, 128, 130};
  pos = binarySearch(vector_entrada, n, 9);
  printf("%d", pos);
}

Diego Adrián Sánchez Gutiérrez

student•

en esta clase vemis como funcionan los algoritmos de busqueda

Cristian Gómez

student•

Seria genial un curso donde solo se hable de estructuras de datos, debido a que es un tema amplio en la informática

Diego Osorio

student•

  	int n = sizeof(vector) / sizeof(vector[0]);

¿que valor retorna sizeof(vector[0])?

Diego Forero

Team Platzi•

Primero es necesario entender que hace sizeof, en c lo que retorna es un entero positivo que denota el tipo de dato. Por ejemplo

sizeof(char)
sizeof(int)
sizeof(double)

Retornaran estos valores

1
4
8

en este caso el sizeof(vector[0]) va a retornar 4 ya que el tipo de dato que esta en la posición 0 es un entero.

Yury D. Morales

student•

Algoritmo de búsqueda: El que obtenga un dato específico dentro de una estructura de datos (lista ordenada, vectores, arreglos)

Yury D. Morales

student•

Binary Search: Parte en 2 la estructura de datos, simplificando la búsqueda. El arreglo ya debe de estar arreglado.

David Andrade Morales

student•

Ojalá esté pronto el curso de estructura de datos!!! De manos de Celis, es un excelente profesor!

Yury D. Morales

student•

Uno de los algoritmos de búsqueda mas populares es el del motor de búsqueda de google, el PageRank

Yury D. Morales

student•

Linear Search o Búsqueda Lineal es el más básico, recorriendo todos tus elementos. Podrá ser tan larga o corta como el número n de datos en el que buscar.

Gibrán Pelayo Miranda

student•

Saludos, aquí está mi código para método de búsqueda binaria:

#include <stdio.h>

int busquedaBinaria(int buscado, int array[], int largo)
{
    int inicio = 0;
    int final = largo - 1;
    while(inicio <= final)
    {
        int mitad = (inicio + final)/2;
        if(array[mitad] == buscado)
            return mitad;
        else if(array[mitad] > buscado)
            final = mitad - 1;
        else
            inicio = mitad + 1;
    }
    return -1;
}

int main()
{
    int pos, i, buscado;
    int array[] = {15, 32, 69, 78, 79, 84, 91, 100, 130, 255};
    int longitud = sizeof(array)/sizeof(array[0]);
    printf("*** Metodo de busqueda binaria ***\n\n");
    printf("El arreglo es: \n{ ");
    for (i=0; i<longitud; i++)
    {
        printf("%d ", array[i]);
    }
    printf("}\n\n");
    printf("Introduce el numero a buscar: ");
    scanf("%d", &buscado);
    pos = busquedaBinaria(buscado, array, longitud);
    if(pos!=-1)
        printf("\nNumero %d esta en la posicion %d del arreglo", buscado, pos);
    else
        printf("Numero %d no existe en el arreglo", buscado);
    return 0;
}

#include <stdio.h>

int binarySearch(int array[], int n, int x)
{
  int min, max, p;
  min = 0;
  max = n;
  while(max >= min)
  {
    p = (max + min) / 2;
    if(array[p] == x)
      return p;
    else if(array[p] < x)
      min = p + 1;
    else
      max = p - 1;
  }

  return -1;
}

int main()
{
  int pos;
  int vector[] = {11, 22, 36, 47, 51, 62, 79, 85, 93, 100};
  int n = sizeof(vector) / sizeof(vector[0]);
  pos = binarySearch(vector, n, 62);
  printf("%d\n", pos);

  return 0;
}

#include <stdio.h>

int search(int vector_entrada[], int n, int x)
{
    int i;
    for(i = 0; i<n;i++)
    {
        if(vector_entrada[i] == x){
            return i;
        }
    }
    return -1;
}

void main()
{
    int pos;
    int n = 10;
    int vector_entrada[] = {10, 12, 13, 23, 87, 129, 20, 87, 91, 22};
    pos = search(vector_entrada, n, 20);
    printf("%d", pos);
}

#include <stdio.h>

int search(int vector_entrada[], int n, int x)
{
  int i;
  for(i=0; i<n; i++)
  {
    if(vector_entrada[i])
    {
      return i;
    }
  }
  return -1;
}

int main()
{
  int pos;
  int n = 10;
  int vector_entrada[] = {1,2,3,4,5,6,7,8,9,55};
  pos = search(vector_entrada, n, 9);
  printf("%d", pos);
}```

#include <stdio.h>

int binarySearch(int vector_entrada[], int n, int x)
{
  int p = 0;
  int r = n;

  while(p <= r){
    m = (p+r)/2
    if(vector_entrada[m] == x){
      return m;
    }
    if (vector_entrada[m] < x) {
      p = mid + 1;
    }else{
      r = mid - 1;
    }
  }
  return -1;
}

int main()
{
  int pos;
  int n = 10;
  int vector_entrada[] = {10, 25, 26, 27, 30, 50, 58, 88, 100, 128, 130};
  pos = binarySearch(vector_entrada, n, 9);
  printf("%d", pos);
}

#include <stdio.h>

int busquedaBinaria(int buscado, int array[], int largo)
{
    int inicio = 0;
    int final = largo - 1;
    while(inicio <= final)
    {
        int mitad = (inicio + final)/2;
        if(array[mitad] == buscado)
            return mitad;
        else if(array[mitad] > buscado)
            final = mitad - 1;
        else
            inicio = mitad + 1;
    }
    return -1;
}

int main()
{
    int pos, i, buscado;
    int array[] = {15, 32, 69, 78, 79, 84, 91, 100, 130, 255};
    int longitud = sizeof(array)/sizeof(array[0]);
    printf("*** Metodo de busqueda binaria ***\n\n");
    printf("El arreglo es: \n{ ");
    for (i=0; i<longitud; i++)
    {
        printf("%d ", array[i]);
    }
    printf("}\n\n");
    printf("Introduce el numero a buscar: ");
    scanf("%d", &buscado);
    pos = busquedaBinaria(buscado, array, longitud);
    if(pos!=-1)
        printf("\nNumero %d esta en la posicion %d del arreglo", buscado, pos);
    else
        printf("Numero %d no existe en el arreglo", buscado);
    return 0;
}

Algoritmos de búsqueda

Introducción al Lenguaje C

¿Dónde aprender C?

Introducción al Lenguaje C

Estructura general de un programa en C y un hola mundo

Tipos de errores y datos en C

Variables en C

Operadores y expresiones en C

Ejemplo de operadores en C y reto

Entrada y salida de datos

Estructura secuencial

Estructura secuencial (if y if else)

Estructura selectiva (if, if else, else)

Estructura selectiva (switch)

Estructuras selectivas anidadas

Más Estructuras Selectivas Anidadas

Estructuras Repetitivas: While

Estructuras repetitivas: Do While

Estructuras Repetitivas: For

Platzi Terminal: Llevando a la Práctica lo Aprendido

Crear una tienda de Platzi dentro de la terminal

Crear una tienda de Platzi dentro de la terminal 2

Introducción a Algoritmos

El mundo de los algoritmos

Introducción al Curso de Algoritmos con C

¿Qué es un algoritmo?

Lenguajes de programación

Elementos de un algoritmo

User defined data types: Estructuras de datos y custom data types

Entrada y salida de información

Metodología para la solución de un algoritmo

Resolución del problema

El porqué del análisis de algoritmos

Cómo comparar algoritmos y ritmo de crecimiento

Estructuras de control y estructuras de control secuenciales

Estructuras de control selectivas

Estructuras de control repetitivas

Algoritmos más Utilizados

Sesiones en vivo del Curso de Algoritmos con C

Algoritmos de Ordenamiento

Algoritmo PID

Divide y Vencerás

Algoritmo de Dijkstra: Introducción a los Grafos

Algoritmos de búsqueda