Thực hiện được các thao tác tìm kiếm dữ liệu một cách hiệu quả
1. Mục tiêu
- Trình bày được mục đích của các thuật toán tìm kiếm
- Trình bày được ý tưởng và các bước thực hiện của thuật toán tìm kiếm tuyến tính
- Triển khai được thuật toán tìm kiếm tuyến tính trên mảng
- Trình bày được ý tưởng và các bước thực hiện của thuật toán tìm kiếm tuyến tính
- Triển khai được thuật toán tìm kiếm nhị phân trên mảng
- Tính toán được độ phức tạp của thuật toán tuyến tính và tìm kiếm nhị phân
- Phân biệt được các tình huống nên sử dụng thuật toán tìm kiếm tuyến tính và tìm kiếm nhị phân
2. Giới thiệu
Tìm kiếm là một trong những thao tác căn bản nhất khi làm việc với dữ liệu. Tìm kiếm khách hàng, tìm kiếm sản phẩm hoặc tìm kiếm các thông tin khác nói chung đều là những tính năng mà ta bắt gặp hằng ngày ở các phần mềm. Ở mức độ giải thuật cũng vậy, các lập trình viên thường xuyên tiếp xúc với những tình huống mà ở đó cần đến việc triển khai thuật toán tìm kiếm: tìm kiếm xem liệu dữ liệu có tồn tại hay không, tìm kiếm vị trí của dữ liệu, tìm kiếm dữ liệu dựa trên một đặc điểm nhất định, v.v.
Ở trong chương này, chúng ta sẽ thảo luận về một số thuật toán tìm kiếm căn bản nhất. Dựa trên các thuật toán này, về sau chúng ta có thể triển khai thêm các thuật toán tìm kiếm phù hợp để đáp ứng được yêu cầu của tình huống cụ thể. Hai thuật toán tìm kiếm mà chúng ta sẽ đề cập đến đó là tìm kiếm tuyến tính và tìm kiếm nhị phân.
Hoàn thành chương này, chúng ta có thể xây dựng được các tính năng cho các ứng dụng phần mềm mà ở đó cần triển khai thao tác tìm kiếm dựa trên các tiêu chí khác nhau.
3. Tìm kiếm tuyến tính
Tìm kiếm tuyến tính là thuật toán mà ở đó chúng ta duyệt dữ liệu lần lượt từ đầu đến cuối để tìm ra phần tử phù hợp với yêu cầu đặt ra. Thuật toán này thuộc nhóm “vét cạn”: chúng ta sẽ cố gắng duyệt và kiểm tra lần lượt tất cả các trường hợp.
Khi thao tác với mảng, việc triển khai thuật toán tìm kiếm tuyến tính khá đơn giản, chỉ cần bắt đầu một vòng lặp ở đầu danh sách và so sánh mỗi phần tử với dữ liệu bạn đang tìm kiếm. Nếu tìm thấy một phần tử phù hợp, quá trình tìm kiếm sẽ kết thúc. Nếu đã duyệt tới cuối danh sách mà không có phần tử nào khớp với giá trị cần tìm thì kết luận dữ liệu tìm kiếm không có trong danh sách.
Giải thuật
- Bắt đầu từ phần tử đầu tiên, so sánh với giá trị muốn tìm, nếu bằng giá trị muốn tìm thì trả về vị trí hiện tại còn nếu không bằng thì chuyển sang phần tử kế tiếp.
- Nếu đến phần tử cuối cùng mà không tìm thấy giá trị nào bằng thì nghĩa là không tìm thấy.
Mã giả
Đầu vào: mảng a có N phần tử và giá trị x là giá trị muốn tìm kiếm
Đầu ra: Trả về vị trí nếu tìm thấy phần tử bằng x, ngược lại trả về -1
Bước 1: i = 0 //bắt đầu từ phần tử đầu tiên của dãy
Bước 2: So sánh a[i] với x, có 2 khả năng
- a[i] = x: Tìm thấy. Trả về i và dừng lại
- a[i] != x: Sang bước 3
Bước 3:
- i = i + 1 //xét tiếp phần tử kế trong mảng
- Nếu i >= N: Hết mảng, trả về -1. Ngược lại: Lặp lại Bước 2.
Ví dụ dưới đây minh họa cách thuật toán tìm kiếm tuyến tính làm việc. Giả sử chúng ta đang tìm phần tử có giá trị 12 trong mảng sau:
So sánh giá trị phần tử ở vị trí i = 0 với 12.
Vì 48 khác 12 nên chuyển sang so sánh với phần tử ở vị trí tiếp theo i = 1.
Vì 83 khác 12 nên chuyển sang so sánh với phần tử ở vị trí tiếp theo i = 2.
Cứ lặp lại các bước như vậy đến khi tìm được phần tử có giá trị bằng 12 đầu tiên thì dừng lại.
Trong trường hợp này, đến vị trí i = 5 thì tìm thấy giá trị 12 như mong muốn, vậy kết quả trả về là 5.
Cài đặt thuật toán tìm kiếm tuyến tính
Hàm seqSearch() sau đây được triển khai để kiểm tra xem dữ liệu data có tồn tại trong mảng arr hay không:
1. function seqSearch(arr, data) {
2. for (var i = 0; i < arr.length; ++i) {
3. if (arr[i] == data) {
4. return true;
5. }
6. }
7. return false;
8. }
Nếu giá trị của biến data được tìm thấy trong mảng, hàm trả về true ngay lập tức. Nếu hàm duyệt tới cuối mảng mà không tìm kiếm một phần tử với giá trị phù hợp, hàm trả về false.
Thuật toán tìm kiếm tuyến tính còn được sử dụng để giải quyết các bài toán khác như tìm vị trí của một giá trị, tìm phần tử có giá trị nhỏ nhất, tìm phần tử lớn nhất trong mảng, v.v.
Xem tiếp>> Chuong 7 Tim kiem nhi phan
Có thể bạn quan tâm>> Cam nang lap trinh can ban danh cho nguoi moi bat dau
