Algoritmos de búsqueda

Algoritmos de búsqueda

Buscar encuentra la posición de un valor objetivo en una estructura de datos.

Búsqueda lineal - O(n)

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1;
}

Búsqueda binaria - O(log n)

Requiere array ordenado. Divide el espacio de búsqueda a la mitad.

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }

  

    
Aprende más
    

      
        
GeeksforGeeks: Searching
        
Aprende búsqueda lineal, binaria y más.
      
      
        
LeetCode: Binary Search
        
Resuelve problemas de búsqueda binaria.
      
    
  

  
  return -1;
}

// Recursive version
function binarySearchRecursive(arr, target, left = 0, right = arr.length - 1) {
  if (left > right) return -1;
  
  const mid = Math.floor((left + right) / 2);
  
  if (arr[mid] === target) return mid;
  if (arr[mid] < target) return binarySearchRecursive(arr, target, mid + 1, right);
  return binarySearchRecursive(arr, target, left, mid - 1);
}

Variantes de búsqueda binaria

// Find first occurrence
function findFirst(arr, target) {
  let left = 0, right = arr.length - 1, result = -1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) {
      result = mid;
      right = mid - 1; // Continue searching left
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return result;
}