Thuật toán JavaScript: Tìm kiếm tuyến tính

Tìm kiếm tuyến tính, còn được gọi là tuần tự hoặc đơn giản, là thuật toán tìm kiếm cơ bản nhất. Cho một cấu trúc dữ liệu, ví dụ một mảng, chúng tôi tìm kiếm một mục bằng cách xem xét tất cả các phần tử, cho đến khi chúng tôi tìm thấy nó.

Cách thực hiện của nó rất đơn giản:

const linearSearch = (list, item) => {
  for (const [i, element] of list.entries()) {
    if (element === item) {
      return i
    }
  }
}

Điều này trả về chỉ mục của mục mà chúng tôi đang tìm kiếm. Thí dụ:

linearSearch(['a', 'b', 'c', 'd'], 'd') //3 (index start at 0)

Nếu chúng ta tìm kiếm 'a', thuật toán sẽ chỉ xem xét phần tử đầu tiên và trả về, vì vậy nó rất nhanh.

Nhưng nếu chúng ta tìm kiếm phần tử cuối cùng, thuật toán cần lặp qua tất cả các mảng. Để tính toán giá trị Big O, chúng tôi luôn xem xét trường hợp xấu nhất.

Nênđộ phức tạp của thuật toánO(n).

Tải xuống miễn phí của tôiSổ tay dành cho Người mới bắt đầu JavaScript


Các hướng dẫn js khác: