CTDL và giải thuật - Tìm vị trí đầu của phần tử X
Nhập vào một số nguyên dương n
, tiếp theo là n
số nguyên lần lượt là các phần tử trong dãy a
, cuối cùng nhập số nguyên x
.
Hãy đưa ra chỉ số đầu tiên của phần tử đầu tiên có giá trị bằng x
, nếu không tồn tại số đó thì trả về -1
.
Ví dụ:
- Test mẫu 1:
Input output 4
1 3 2 1
10
Vớia = [1, 3, 2, 1]
vàx = 1
thì kết quả mong muốn là0
.
- Test mẫu 2:
Input Output 3
1 2 3
4-1
Vớia = [1, 2, 3]
vàx = 4
thì kết quả mong muốn là-1
.
Lý thuyết
Giới thiệu về tìm kiếm tuyến tính (Linear Search).
Linear Search là một giải thuật tìm kiếm rất cơ bản. Trong kiểu tìm kiếm này, một hoạt động tìm kiếm liên tiếp được diễn ra qua tất cả từng phần tử. Mỗi phần tử đều được kiểm tra và nếu tìm thấy bất kỳ kết nối nào thì phần tử cụ thể đó được trả về; nếu không tìm thấy thì quá trình tìm kiếm tiếp tục diễn ra cho tới khi tìm kiếm hết dữ liệu.
Ví dụ như muốn tìm chỉ số đầu tiên của phần tử có giá trị 10
trong dãy a = [3, 5, 10, 4]
ta thực hiện các bước sau:
Kiểm tra phần tử thứ nhất a[0] = 3
, không bằng 10
ta tiếp tục kiểm tra phần tử tiếp theo.
Ta kiểm tra a[1] = 5
, không bằng 10
ta tiếp tục kiểm tra phần tử tiếp theo.
Ta kiểm tra a[2] = 10
, lúc này ta đã tìm thấy phần tử đầu tiên bằng 10
, đó là phần tử ở chỉ số thứ 2
, trong trường hợp duyệt hết dãy mà vẫn không tìm thấy giá trị 10
thì dãy đó không tồn tại giá trị đó.
Code C++ mẫu:
int search(int a[], int n, int x){
for (int i = 0; i < n; i++){
if (a[i] == x){
return i;
}
}
return -1;
}
Việc đưa ra phần tử cuối cùng cũng tương tự, ta có duyệt dãy theo chiều ngược lại.
int search(int a[], int n, int x){
for (int i = n-1; i >= 0; i--){
if (a[i] == x){
return i;
}
}
return -1;
}
Hoặc làm như sau:
int search(int a[], int n, int x){
int k = -1;
for (int i = 0; i < n; i++){
if (a[i] == x){
k = i;
}
}
return k;
}
Hướng dẫn bài tập.
Code mẫu:
Ngôn ngữ C++:
#include<iostream>
using namespace std;
int search(int a[], int n, int x){
for (int i = 0; i < n; i++){
if (a[i] == x){
return i;
}
}
return -1;
}
int a[100001];
int main(){
int n, x;
cin >> n;
for (int i = 0; i < n; i++){
cin >> a[i];
}
cin >> x;
cout << search(a, n, x);
return 0;
}