/codegym.vn/ - 142
Cài đặt thuật toán tìm kiếm nhị phân
1.
function
binarySearch
(
data
,
intArray
)
{
2.
let
lowerBound
=
0
;
// chỉ số đầu
3.
let
upperBound
=
intArray
.
length
-
1
;
// chỉ số cuối
4.
let
midPoint
=
-
1
;
// chỉ số giữa
5.
let
index
=
-
1
;
// vị trí tìm thấy giá trị cần tìm trong mảng
6.
7.
while
(
lowerBound
<=
upperBound
)
{
8. midPoint
=
Math
.
floor
((
lowerBound
+
upperBound
)
/
2
);
9.
if
(
intArray
[
midPoint
]
==
data
)
{
10. index
=
midPoint
;
11.
break
;
12.
}
else
{
13.
if
(
intArray
[
midPoint
]
<
data
)
{
14. lowerBound
=
midPoint
+
1
;
15.
}
else
{
16. upperBound
=
midPoint
-
1
;
17.
}
18.
}
19.
}
20.
return
index
;
21.
}
22.
5. Độ phức tạp của thuật toán
Độ phức tạp thuật toán là một mô hình tính toán để đánh giá mức độ tiêu tốn tài
nguyên hệ thống của một thuật toán, bởi vì tài nguyên cần dùng phụ thuộc vào kích
cỡ của dữ liệu đầu vào, chúng ta có thể xem độ phức tạp thuật toán là một hàm đặc
trưng cho động thái của hệ thống khi kích cỡ đầu vào tăng lên. Thường chúng ta
không cần tìm cách xác định chính xác tuyệt đối những hàm này mà chỉ cần tìm ra
một ước lượng đủ tốt của chúng.
Để ước lượng độ phức tạp của một thuật toán ta thường dùng khái niệm bậc O-lớn
và bậc Θ (đọc là bậc Theta). Chúng ta có thể coi chúng là những hàm tiệm cận với
hàm tính độ phức tạp thuật toán.
Để diễn giải khái niệm bậc O và bậc Theta, trong mục này chúng ta gọi độ lớn của dữ
liệu đầu vào là n.
