Thuật toán tìm kiếm tuyến tính trong PHP

Trong bài này chúng ta sẽ tìm hiểu thuật toán tìm kiếm tuyến tính trước, nội dung bìa học như sau:

  • Tìm kiếm tuyến tính là gì?
  • Các ví dụ tìm kiếm tuyến tính
1. Tìm kiếm tuyến tính là gì?

Tìm kiếm tuyến tính (hay tìm kiếm tuần tự) là một thuật toán tìm kiếm một phần tử cho trước nằm trong một danh sách (có thể là mảng) bằng cách duyệt lần lược các phần tử và so sánh cho đến khi tìm thấy phần tử đó.

Giả sử có mảng $a gồm 50 phần tử, giờ tìm xem số 50 có nằm trong mảng không thì ta sẽ dùng vòng lặp for để duyệt lần lược 50 phần tử đó và so sánh xem có phần tử nào bằng 50 không. Nếu có thì trả kết quả là tìm thấy và dừng vòng lặp, ngược lại nếu lặp hể cả 50 phần tử mà vẫn không có thì sẽ trả kết quả là không tìm thấy.

Tìm kiếm tuyến tính tuần tự là một giải thuật rất đơn giản và dễ cài đặt, giải thuật này tỏ ra khá là nhanh đối với những dữ liệu có kích thước nhỏ vừa phải chưa được sắp thứ tự.

2. Ví dụ tìm kiếm tuyến tính

Trong phần này chúng ta sẽ làm các ví dụ tìm kiếm tuyến tính trong php, qua đó các bạn sẽ hiểu được ý tưởng của nó.

Ví dụ 1: Cho mảng $mang = array(321,312,3,4,5,45,56,5,7,6,787,8,7,2); Hãy viết hàm kiểm tra số 67 có nằm trong mảng không?

Chúng ta sẽ giải bài toán bằng hai cách không dùng hàm và có dùng hàm.

Giải không dùng hàm:

Giải có dùng hàm:

Ví dụ 2: Cho một mảng gồm các phần tử từ 1 đến 100. Hãy tìm vị trí các số chia hết cho 3 trong dãy

Nguồn: freetuts.net

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *