Tìm kiếm nhị phân (Binary Search)

Bài toán tìm kiếm một đối tượng trong dãy đối tượng mà có khóa bằng một khóa cho trước.
Binary Search
Thuật toán tìm kiếm nhị phân dùng để tìm kiếm phần tử trong một danh sách đã được sắp xếp, ví dụ như trong một danh bạ điện thoại sắp xếp theo tên, có thể tìm kiếm số điện thoại của một người theo tên người đó.

Thuật toán tìm kiếm nhị phân chạy nhanh hơn tìm kiếm tuyến tính nhưng cũng có một số nhược điểm. Tìm kiếm nhị phân có thể chậm hơn bảng băm. Nếu nội dung danh sách bị thay đổi thì danh sách phải được sắp xếp lại trước khi sử dụng tìm kiếm nhị phân. Thao tác này thường tốn nhiều thời gian.

Tham khảo thêm tại blog's KienNTT

Một số bài tập luyện tập VN.SPOJ.VN

  1. http://vn.spoj.com/problems/MOVE12/
  2. http://vn.spoj.com/problems/LEM1/
  3. http://vn.spoj.com/problems/CRUELL2/
  4. http://vn.spoj.com/problems/NDCCARD/
  5. http://vn.spoj.com/problems/TOTALODD/
  6. http://vn.spoj.com/problems/VOPIG/
  7. http://vn.spoj.com/problems/NKSGAME/
  8. http://vn.spoj.com/problems/QBROBOT/
  9. http://vn.spoj.com/problems/DGOLD/
  10. http://vn.spoj.com/problems/C11POST/
  11. http://vn.spoj.com/problems/VOGCDSUM/
  12. http://vn.spoj.com/problems/VMCANDLE/
  13. http://vn.spoj.com/problems/PRAVO/
  14. http://vn.spoj.com/problems/ASSIGN1/
  15. http://vn.spoj.com/problems/MTWALK/
  16. http://vn.spoj.com/problems/NK05ORDR
  17. http://vn.spoj.com/problems/RIDDLE/

Luyện tập tại NTUCoders:

Comments

Post a Comment

Popular posts from this blog

Bài toán dãy tìm con liên tiếp

Image
Thuật toán chia để trị: ta chia bài toán cần giải quyết thành nhiều bài toán con, giải quyết từng bài toán con, sau đó ta tổng hợp lại để giải bài toán lớn. Thuật toán chia để trị được biết đến tiêu biểu qua giải thuật merge-sort… Mặc dù nó được ứng dụng khá nhiều, nhưng nó không có một cách giải quyết tổng quát cho các bài toán. Ta phải hiểu tư tưởng của nó và áp dụng vào từng trường hợp cụ thể. Trong bài viết này, tôi sẽ trình bày một trường hợp áp dụng thuật toán chia để trị, tuy chỉ là một trường hợp áp dụng, nhưng dạng này ta gặp rất thường xuyên. Ta sẽ đi đi từ bài toán tổng quát, rồi áp dụng vào ví dụ cụ thể. Bài toán tổng quát : ta tìm một dãy con liên tiếp trong dãy đã cho để thỏa mãn một tính chất nào đó. Cách giải quyết : Thông thường với kích thước của dãy khoảng N=10^3, ta dùng hai vòng lặp chạy lồng nhau với độ phức tạp O(N^2) để xét tất cả dãy con và tìm ra dãy con phù hợp nhất. Khi N lớn hơn một chút, tầm khoảng N=10^5, ta phải có một giải thuậ...
Read more

Hướng dẫn cách Debug trong Free Pascal

Image
Trong quá trình lập trình, chắc hẳn trong chúng ta ai cũng sẽ không tránh được các lỗi trong chương trình của mình (lỗi cú pháp, lỗi thuật toán, . . . ). Nhưng máy tính thì thực hiện những đoạn chương trình của chúng ta rất nhanh có thể là trong vài giây thậm chí vài mili giây. Vậy thì làm sao chúng ta có thể phát hiện ra những dòng code lỗi trong hàng trăm, hàng nghìn dòng code mà ta đã viết ??? Rất may mắn là trong hầu hết các IDE của các ngôn ngữ lập trình đều hỗ trợ một chức năng rất hay được gọi là Debug, bạn có thể gọi là “bắt bọ” hay chạy từng bước đều được  :)  . Trong bài viết này, tôi sẽ hướng dẫn các bạn làm thế nào để Debug trong IDE Free Pascal. Để Debug được thì bạn cần nắm một số thuật ngữ cơ bản sau : Debug : bắt lỗi, “dò bọ”, “bắt bọ”. Watch : nơi bạn xem sự thay đổi giá trị của các biến. BreakPoint : điểm (dòng) mà bạn sẽ bắt IDE dừng ở đó để bạn xem trạng thái hiện tại của chương trình hay giá trị của các biến. Để bắt đầu quá trình Debug thì...
Read more