So sánh
Bước nhảy
Tìm kiếm tuyến tính cần

  • Mục tiêu
  • Khối đang xét
  • Đang so sánh
  • Đã loại
  • Đã tìm thấy

Tìm hiểu thêm về tìm kiếm nhảy bước

Tìm kiếm nhảy bước

Tìm kiếm nhảy bước nằm giữa tìm kiếm tuyến tính và tìm kiếm nhị phân. Nó đi qua danh sách đã sắp xếp theo từng bước nhảy m vị trí, chỉ kiểm tra giá trị cuối của mỗi khối, cho đến khi gặp khối có giá trị cuối không nhỏ hơn mục tiêu. Rồi nó quét khối đó từ đầu. Chọn giá trị và bước nhảy, rồi xem các bước nhảy và lần quét cần bao nhiêu phép so sánh. Nhấn Phát để xem quá trình tìm kiếm, hoặc Bước và Lùi để đi từng phép so sánh. Kéo thanh trượt bước để nhảy đến bất kỳ đâu. Đường nét đứt đánh dấu giá trị cần tìm, còn phần tô bóng là khối đang xét. Tìm kiếm nhảy bước cần danh sách đã sắp xếp, nên danh sách chưa sắp xếp sẽ được sắp xếp trước. Chọn giá trị, bước nhảy, số cột, hoặc tự nhập các số. Khi bảng được chọn, phím mũi tên đi từng bước, phím cách phát và tạm dừng, còn Home và End nhảy về đầu và cuối.

Cách nó hoạt động

  1. Chọn giá trị cần tìm, bước nhảy và số cột. Hoặc tự nhập các số: tìm kiếm nhảy bước sẽ sắp xếp chúng trước.
  2. Nhấn Phát, hoặc dùng Bước và Lùi để đi từng phép so sánh. Kéo thanh trượt bước để nhảy đến bất kỳ đâu trong quá trình tìm kiếm.
  3. Thử bước nhảy 2 và 8 với 40 cột, rồi so số phép so sánh với khi dùng √n.

Cách tìm kiếm nhảy bước hoạt động

Chia danh sách đã sắp xếp thành các khối m giá trị. Xem giá trị cuối của khối đầu tiên. Nếu nó nhỏ hơn mục tiêu, mục tiêu không thể nằm ở đâu trong khối đó, nên nhảy đến cuối khối kế tiếp và xem lại. Ngay khi giá trị cuối của một khối không nhỏ hơn, mục tiêu chỉ có thể nằm trong khối đó: quay về đầu khối và kiểm tra từng giá trị cho đến khi tìm thấy mục tiêu hoặc vượt qua nó.

Chọn bước nhảy

Với n giá trị, các bước nhảy cần tối đa n/m phép so sánh và lần quét tối đa m. Bước nhảy nhỏ làm lần quét ngắn nhưng phải nhảy nhiều lần; bước nhảy lớn thì ngược lại. Tổng n/m + m nhỏ nhất khi m = √n, cho khoảng 2√n phép so sánh: tối đa 13 với 40 giá trị, so với 40 của tìm kiếm tuyến tính và 6 của tìm kiếm nhị phân. Tìm kiếm nhảy bước không bao giờ lùi quá một khối, điều này có ích khi việc đi lùi trong dữ liệu chậm.

Câu hỏi thường gặp

Tìm kiếm nhảy bước hoạt động thế nào?

Trên danh sách đã sắp xếp, nó nhảy tới từng bước m vị trí và kiểm tra giá trị cuối của mỗi khối. Khi giá trị đó không còn nhỏ hơn mục tiêu, mục tiêu chỉ có thể nằm trong khối đó, và nó quét khối từ đầu.

Bước nhảy tốt nhất là bao nhiêu?

√n, làm tròn. Các bước nhảy tốn tối đa n/m phép so sánh và lần quét tối đa m, tổng của chúng nhỏ nhất khi hai phần bằng nhau, tại m = √n. Khi đó trường hợp xấu nhất cần khoảng 2√n phép so sánh.

Tìm kiếm nhảy bước có nhanh hơn tìm kiếm nhị phân không?

Không, tìm kiếm nhị phân cần ít phép so sánh hơn: khoảng log₂ n so với khoảng 2√n. Tìm kiếm nhảy bước vẫn có thể hơn khi việc đi lùi trong dữ liệu tốn kém, vì nó chỉ lùi một lần, về đầu một khối.

Khi có giá trị lặp lại, nó tìm thấy giá trị nào?

Giá trị đầu tiên. Mọi khối bị bỏ qua đều kết thúc bằng một giá trị nhỏ hơn mục tiêu, nên không khối nào trước đó có thể chứa giá trị khớp, và lần quét bắt đầu từ đầu khối.

Các số của tôi có bị gửi đi đâu không?

Không. Việc tìm kiếm chạy trong trình duyệt của bạn, và các thiết lập gần nhất được lưu trong bộ nhớ cục bộ của trình duyệt này.

Sẵn sàng thử chưa?

Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.

Tới trình chỉnh sửa