Các thư viện tiêu chuẩn giữ lại lập trình viên từ việc đổi mới lại cái bánh xe. Steve McConnell
STDIO Tìm kiếm là một nhu cầu thiết yếu trong cuộc sống, và đương nhiên, cũng không phải là ngoại lệ trong lập trình. Tôi sẽ bắt đầu với thuật toán tìm kiếm đơn giản nhất: Sequential search – Tìm kiếm tuần tự hay Linear search – Tìm kiếm tuyến tính.
Nội dung bài viết

Giới thiệu

Tìm kiếm là một nhu cầu thiết yếu trong cuộc sống, và đương nhiên, cũng không phải là ngoại lệ trong lập trình. Chúng ta có rất nhiều thuật toán để thực hiện thao tác tìm kiếm. Để mở đầu cho chuỗi bài viết về các thuật toán tìm kiếm, tôi sẽ bắt đầu với thuật toán tìm kiếm đơn giản nhất Sequential search – Tìm kiếm tuần tự hay Linear search – Tìm kiếm tuyến tính.

Linear Search

Ý tưởng

Bạn hãy tưởng tượng rằng, bạn có một chiếc chìa khóa và một tập hợp các ổ khóa. Nhiệm vụ của bạn là phải kiếm xem có hay không ổ khóa vừa chiếc chìa khóa trên tay. Cách đơn giản nhất đó là, chúng ta sẽ thử chiếc chìa khóa với từng ổ khóa cho tới khi nhận được kết quả.

ss_1

Hiện thực

void LinearSearch(int arr[], int numberOfElements, int key)
{
	int index = 0;
	bool isKeyFound = false;
	
	for (index; index < numberOfElements; index++)
	{
		if(arr[index] == key)
		{
			printf("%d is found at index %d\n", key, index);
			isKeyFound = true;
		}
	}

	if (index == numberOfElements && isKeyFound == false)
		printf("There is no %d in array.\n", key);
}

Ở đây, tôi đưa ra một mảng arr gồm 9 phần tử, và cần tìm kiếm phần tử có giá trị key = 5 trong mảng này.

Các bước thực hiện

  • Bước 1: Duyệt mảng từ vị trí đầu tiên - index = 0.
  • Bước 2: Thực hiện so sánh arr[index] và key. Nếu arr[index] == key thì in ra dòng chữ xác nhận tìm thấy key và in ra vị trí tìm thấy (index). Đồng thời bật cờ isKeyFound để đánh dấu trong mảng có ít nhất 1 vị trí tồn tại key.
  • Bước 3: Nếu index == numberOfElements tức đã duyệt mảng xong và isKeyFound == false (mảng không tìm thấy vị trí nào chứa key), thì in ra thông báo trong mảng không tồn tại key.

Đánh giá

  • Trong trường hợp tốt nhất, phần tử cần tìm nằm ở vị trí đầu tiên, thuật toán sử dụng 1 lần so sánh.
  • Trong trường hợp xấu nhất, phần từ cần tìm nằm ở vị trí cuối, hoặc không thuộc trong mảng, thuật toán sử dụng n-1 lần so sánh.
  • Linear Search là một giải thuật đơn giản khi hiện thực và khá hiệu quả với danh sách đủ nhỏ hoặc một danh sách chưa được sắp xếp đơn giản.

Bạn có thể download mã nguồn và tham khảo thêm các giải thuật tìm kiếm hữu ích khác theo đường dẫn.

Bạn cần hỗ trợ các dự án kết nối không dây?

Quí doanh nghiệp, cá nhân cần hỗ trợ, hợp tác các dự án IoT, kết nối không dây. Vui lòng liên hệ, hoặc gọi trực tiếp 0942.111912.

  • TỪ KHÓA
  • Arduino
  • ESP32
  • ESP8266
  • Wifi
  • Bluetooth
  • Zigbee
  • Raspberry Pi
THẢO LUẬN
ĐÓNG