Khi phát triển các thuật toán để giải quyết nhiều vấn đề, vấn đề thường nảy sinh là thực hiện tìm kiếm một nhóm dữ liệu nhất định theo các tiêu chí xác định. Khi khám phá một trình tự có thứ tự hoặc không có thứ tự, việc tìm kiếm có thể được thực hiện bằng các phương pháp khác nhau. Trong trường hợp tổng quát, để giải quyết vấn đề tìm kiếm, một mảng dữ liệu nhất định được xem xét, trong đó nó bắt buộc phải tìm một phần tử đã cho.
Hướng dẫn
Bước 1
Cách dễ nhất để tìm một phần tử đã biết trong mảng dữ liệu là lặp lại các giá trị của nó. Thuật toán này là tối ưu cho lượng thông tin nhỏ. Bản chất của nó nằm ở việc duyệt qua một chuỗi (mảng) dữ liệu đã biết và so sánh từng phần tử với giá trị mong muốn. Nếu tìm thấy kết quả phù hợp, tùy thuộc vào tiêu chí đã chỉ định, tìm kiếm có thể được hoàn thành hoặc tiếp tục đến cuối mảng.
Bước 2
Tuy nhiên, mặc dù sự đơn giản của việc thực hiện phương pháp này, việc sử dụng nó là không mong muốn trong các mảng chứa lượng lớn thông tin, vì điều này làm tăng đáng kể cường độ tài nguyên của thuật toán. Để tối ưu hóa việc tìm kiếm trong trường hợp này, tốt hơn là nên sắp xếp trước các giá trị trong mảng và thực hiện các thuật toán tìm kiếm: theo cây nhị phân, theo cây Fibonacci, bằng phương pháp ngoại suy.
Bước 3
Khi làm việc với một mảng có thứ tự, hãy sử dụng một thuật toán hiệu quả hơn - phương pháp tìm kiếm nhị phân. Bản chất của nó nằm ở chỗ, trong quá trình liệt kê các ranh giới của các khoảng tiến lại gần nhau, do đó sẽ thu hẹp vùng tìm kiếm. So sánh giá trị bạn đang tìm kiếm với phần tử được đánh số của mảng. Nếu mẫu phù hợp với phần tử, vấn đề được coi là đã được giải quyết. Nếu mục mong muốn lớn hơn phần tử giữa, thì phải tiến hành tìm kiếm thêm trong phần của mảng nằm ở bên phải phần tử giữa (từ đầu mảng đến phần tử giữa-1). Nếu tìm kiếm nhỏ hơn phần tử ở giữa, thì việc tìm kiếm sẽ tiếp tục trong phần của mảng từ phần tử giữa đến phần tử cuối cùng. Sau khi xác định một khu vực mới để tìm kiếm, thuật toán được mô tả được lặp lại, xác định các kết quả phù hợp hoặc thu hẹp khu vực xử lý. Lược đồ này đúng cho một mảng giảm dần.
Bước 4
Các bài toán cụ thể về việc tìm phần tử nhỏ nhất hoặc lớn nhất trong một dãy đã cho được giải quyết bằng cách gán phần tử ban đầu như phần tử mong muốn. Tiếp theo, liệt kê tuần tự các giá trị còn lại của mảng được thực hiện: giá trị thứ hai với giá trị đầu tiên, thứ ba với giá trị đầu tiên, v.v. Khi so sánh giá trị được lấy làm tiêu chuẩn, sẽ rõ ràng liệu có phần tử nào trong mảng phù hợp hơn với điều kiện đã cho (tối thiểu hoặc tối đa) hay không. Khi một cái được tìm thấy, nó đã được lấy làm tiêu chuẩn và việc liệt kê tiếp tục từ vị trí hiện tại đến cuối mảng. Do đó, giá trị nhỏ nhất (hoặc lớn nhất) trong nhóm này là phần tử được công nhận lần cuối là tiêu chuẩn.
