/codegym.vn/ - 140
Việc tìm kiếm sẽ được tiếp tục cho tới khi tìm hết các phần tử trên tập dữ liệu con.
Giải thích thuật toán bằng hình minh hoạ
Trong hình minh hoạ trên, chúng ta có:
● lowerBound là vị trí của phần tử đầu tiên
● upperBound là vị trí của phần tử cuối cùng
● midPoint là vị trí của phần tử ở giữa (midPoint bằng trung bình cộng của
lowerBound và upperBound)
Giả sử x là phần tử cần tìm, vậy chúng ta so sánh x với giá trị tại midPoint. Có 3 khả
năng xảy ra:
● Nếu x bằng với giá trị tại midPoint thì trả về giá trị đó, kết thúc thuật toán
● Nếu x nhỏ hơn giá trị tại midPoint thì rõ ràng là x phải nằm trong khoảng
[lowerBound – midPoint], và như vậy thì chúng ta có thể loại bỏ khoảng
[midPoint – upperBound].
● Nếu x lớn hơn giá trị tại midPoint thì rõ ràng là x phải nằm trong khoảng
[midPoint – upperBound], và như vậy thì chúng ta có thể loại bỏ khoảng
[lowerBound – midPoint].
Mã giả
1.
begin
2. A
// mảng đã được sắp xếp
3. n
// kích cỡ mảng
4. x
// giá trị để tìm kiếm trong mảng
5. lowerBound
=
0
// chỉ số đầu của mảng
6. upperBound
=
n
-
1
// chỉ số cuối của mảng
7.
8.
while
x
not
found
9.
if
upperBound
<
lowerBound
10.
EXIT
:
x kh
ô
ng t
ồ
n t
ạ
i
.
11. midPoint
=
(
lowerBound
+
upperBound
)
/
2
12.
if
A
[
midPoint
]
<
x
13. lowerBound
=
midPoint
+
1
14.
15.
if
A
[
midPoint
]
>
x
16. upperBound
=
midPoint
-
1
17.
if
A
[
midPoint
]
=
x
18. EXIT
:
x
đượ
c t
ì
m th
ấ
y t
ạ
i midPoint
19.
end
while
20.
end
21.
Ví dụ:
