/codegym.vn/ - 139
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
(
let
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.
4. Tìm kiếm nhị phân
Tìm kiếm nhị phân (binary search) là một giải thuật tìm kiếm nhanh với độ phức tạp
thời gian chạy là O(log n). Giải thuật tìm kiếm nhị phân làm việc dựa trên nguyên tắc
chia để trị. Để thuật toán tìm kiếm nhị phân có thể hoạt động trên một tập dữ liệu thì
tập dữ liệu đó phải được sắp xếp.
Giải thuật
Binary Search tìm kiếm một giá trị xác định bằng cách so sánh giá trị đó với giá trị của
phần tử tại vị trí giữa của tập dữ liệu. Có 3 trường hợp xảy ra:
● Nếu giá trị cần tìm bằng với hơn giá trị của phần tử ở giữa của tập dữ liệu thì
trả về phần tử đó.
● Nếu giá trị cần tìm lớn hơn giá trị của phần tử ở giữa của tập dữ liệu thì giá trị
cần tìm sẽ được tìm trong tập dữ liệu con nằm bên phải phần tử giữa.
● Nếu giá trị cần tìm nhỏ hơn giá trị của phần tử ở giữa của tập dữ liệu thì giá trị
cần tìm sẽ được tìm trong tập dữ liệu con nằm bên trái phần tử giữa.
