В предыдущей статье Insight from Harvard Cs50 (1) я кратко коснулся концепций, рассмотренных в лекции 3 об алгоритмах, чтобы позже объяснить больше здесь! Давайте погрузимся прямо в!

Следующие примечания дополнены соответствующими временными метками видео:

Если вы нашли определенный элемент в списке:

00:13:02линейный поиск(O(n): линейная временная сложность)

function linearSearch(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) {
            return i; // Return the index where the target is found
        }
    }
    return -1; // Return -1 if target is not found
}

const arr = [3, 7, 2, 8, 5];
const target = 8;
const index = linearSearch(arr, target);

if (index !== -1) {
    console.log(`Target ${target} found at index ${index}`);
} else {
    console.log(`Target ${target} not found in the array`);
}

00:22:57Двоичный поиск (O(log n): логарифмическая временная сложность)

Если число отсортировано с предположением,используются условные операторы (if-else) и рекурсия вместо использования традиционного цикла (линейный поиск).

//iterative version of the binary search algorithm using a loop
function binarySearch(arr, x) {
    let low = 0;
    let high = arr.length - 1;

    while (low <= high) {
        let mid = Math.floor((low + high) / 2);

        if (arr[mid] === x) {
            return true; // Element found
        } else if (arr[mid] < x) {
            low = mid + 1; // Search the right half
        } else {
            high = mid - 1; // Search the left half
        }
    }

    return false; // Element not found
}

так что такое рекурсия?

Представьте, как ваша мама избивает вас, ребята (извините, память азиатских детей 90-х): сначала старший брат, затем младший, затем вы и, наконец, ваша младшая сестра. В то время как и циклы, и рекурсия повторяют действия, рекурсия разбивает вещи от большего к меньшему, следуя определенным правилам (в отличие от поиска через двери).

Рекурсия позволяет избежать использования явных циклов, в то время как двоичный поиск может быть реализован с использованием либо рекурсии, либо циклов сопределенными правилами для сужения поиска.

function binarySearchRecursive(arr, target, low, high) {
    if (low > high) {
        return -1; // Base case: target not found
    }

    let mid = Math.floor((low + high) / 2);

    if (arr[mid] === target) {
        return mid; // Base case: target found at index mid
    } else if (arr[mid] < target) {
        return binarySearchRecursive(arr, target, mid + 1, high); // Search right half
    } else {
        return binarySearchRecursive(arr, target, low, mid - 1); // Search left half
    }
}

const arr = [2, 4, 6, 8, 10, 12, 14, 16];
const target = 10;

const index = binarySearchRecursive(arr, target, 0, arr.length - 1);

if (index !== -1) {
    console.log(`Target ${target} found at index ${index}`);
} else {
    console.log(`Target ${target} not found in the array`);
}

рекурсия будет позже обсуждаться, давайте двигаться дальше.

00:51:21 — структуры

Используется для обозначения пользовательского типа данных с несколькими полями, вы можете провести сравнение с тем, как интерфейсы TypeScript работают в JavaScript.

//a struct in C
struct Student {
    int id;
    char name[50];
    float gpa;
};

//in TS
interface Student {
    id: number;
    name: string;
    gpa: number;
}

— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —

Если вы хотите отсортировать список элементов:

Два неудачных способа:

01:14:41 — Сортировка выбором (O(n²))

function selectionSort(arr) {
  const n = arr.length;
//check all 
  for (let i = 0; i < n - 1; i++) {
    let minIndex = i;
//get the next compare number from the loop i itself
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }

    if (minIndex !== i) {
      // Swap elements
      const temp = arr[i];
      arr[i] = arr[minIndex];
      arr[minIndex] = temp;
    }
  }

  return arr;
}

const unsortedArray = [64, 34, 25, 12, 22, 11, 90];
const sortedArray = selectionSort(unsortedArray);

console.log("Unsorted array:", unsortedArray);
console.log("Sorted array:", sortedArray);

01:36:22 — пузырьковая сортировка (O(n²))

function bubbleSort(arr) {
  const n = arr.length;

  for (let i = 0; i < n - 1; i++) {
    // Last i elements are already in place, no need to compare them
    for (let j = 0; j < n - i - 1; j++) {
      // Compare adjacent elements and swap if necessary
      if (arr[j] > arr[j + 1]) {
        const temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }

  return arr;
}

const unsortedArray = [64, 34, 25, 12, 22, 11, 90];
const sortedArray = bubbleSort(unsortedArray);

console.log("Unsorted array:", unsortedArray);
console.log("Sorted array:", sortedArray);

Реализация использования рекурсии более эффективна, чем описанная выше.

01:54:32 — Рекурсия (разделяй и властвуй)

  1. Разделить: несортированный список делится на две половины.
  2. Завоевание: каждая половина рекурсивно сортируется с использованием одного и того же алгоритма.
  3. Объединить: отсортированные части объединяются вместе, чтобы получить окончательный отсортированный список.

02:04:22 — Сортировка слиянием (O(n log n))

Большой бинарный поиск = алгоритмы «разделяй и властвуй» (слияние, быстрота, алгоритм Штрассена)

function mergeSort(arr) {
  if (arr.length <= 1) {
    return arr; // Base case: already sorted or single element
  }

  const middle = Math.floor(arr.length / 2);
  const leftHalf = arr.slice(0, middle);
  const rightHalf = arr.slice(middle);

  return merge(mergeSort(leftHalf), mergeSort(rightHalf));
}

function merge(left, right) {
  let result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }

  return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

const unsortedArray = [64, 34, 25, 12, 22, 11, 90];
const sortedArray = mergeSort(unsortedArray);

console.log("Unsorted array:", unsortedArray);
console.log("Sorted array:", sortedArray);