Viết hai hàm tìm kiếm tuần tự khác nhau

113 · September 23, 2019, 3:05pm

Yêu cầu tìm kiếm vị trí của giá trị key cho trước. Trả về vị trí đầu tiên tìm được. Nếu không tìm được trả về −1.

Tìm kiếm tuần tự: • int LinearSearch(int* a, int n, int key);
Tìm kiếm tuần tự (sử dụng phương pháp lính canh): • int sentinelLinearSearch(int* a, int n, int key);
Em làm xong bài 1 cái nhìn xuống bài 2 thì không biết làm gì nữa (bài 1 làm giống bài 2). Có anh chị nào giúp em bài một không có phải dùng kĩ thuật cờ hiệu không ạ.

SITUVN.gcd · September 23, 2019, 3:46pm

Lính canh dùng để tìm lớn/nhỏ nhất, áp dụng bài này kiểu gì nhể.
Cờ hiệu thì có thể áp dụng vào bài này. Duyệt từ cuối và gán vào cờ (kiểu int) đến đầu (0) thì trả về. Có thể xem là làm ngược lại của bài 1.

rogp10 · September 23, 2019, 4:03pm

Lính canh là thêm phần tử vào đầu/cuối đó bạn

SITUVN.gcd · September 23, 2019, 5:56pm

A post was merged into an existing topic: Topic lưu trữ các post off-topic - version 3

113 · September 23, 2019, 5:53pm

như này có đúng không ạ.

 int LinearSearch(int* a, int n, int key) {
     int i = 0;
     while (key != a[i] && i < n) {
	     i++;
     }

     if (i != n) {
	     return i;
     }
     else {
	     return -1;
     }

}

int SentinelLinearSearch(int* a, int n, int key) {
    int linhcanh = key;

    for (int i = 0; i < n; i++) {

	    if (linhcanh == a[i]) {
		   return i;
		   break;
	    }

    }

    return -1;
}