• Trang Chủ
  • Top Source
  • Source miễn phí
  • Source Tham Khảo
  • Kiến Thức
  • Thư Viện
  • Trang Chủ
  • Top Source
  • Source miễn phí
  • Source Tham Khảo
  • Kiến Thức
  • Thư Viện

Thụât toán tìm kiếm nhị phân (Binary Search)

ContentATP Bởi ContentATP
24/08/2020
Trong Kiến Thức
0
Thuat Toan Tim Kiem Nhi Phan Binary Search

Trong bài đăng này chúng ta sẽ tìm hiểu về thuật toán tìm kiếm nhị phân (Binary search). Đây chính là thụât toán rộng rãi để tìm kiếm vị trí một phần tử trong một mảng đã bố trí.

Mục lục

  • Giải thuật tìm kiếm nhị phân (Binary Search) là gì ?
    • 1. Tìm kiếm nhị phân (Binary Search)
    • 2. Ý tưởng thụât toán
    • 3. Triển khai thụât toán
  • Ý tưởng của thuật toán tìm kiếm nhị phân
  • Tóm lại

Giải thuật tìm kiếm nhị phân (Binary Search) là gì ?

Tìm kiếm nhị phân
Tìm kiếm nhị phân

Binany Search (Tìm kiếm nhị phân) là một giải thuật tìm kiếm nhanh với độ phức tạp thời gian chạy là Ο(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ị (Divide and Conquer). Để giải thuật này có thể làm việc một cách rõ ràng thì tập dữ liệu có thể ở trong dạng đã được sắp đặt.

Binary Search tìm kiếm một phần tử chi tiết bằng cách so sánh phần tử tại vị trí giữa nhất của tập dữ liệu. Nếu tìm thấy liên kết chặt chẽ thì chỉ mục của phần tử được trả về. Nếu như phần tử cần tìm là lớn hơn thành quả phần tử giữa thì phần tử cần tìm được tìm trong mảng con nằm ở bên phải phần tử giữa; nếu không thì sẽ tìm ở trong mảng con nằm ở bên trái phần tử giữa. Tiến trình sẽ lặp lại như vậy trên mảng con cho tới khi tìm hết mọi phần tử trên mảng con này.

1. Tìm kiếm nhị phân (Binary Search)

Thụât toán tìm kiếm nhị phân (Binary Search) hay còn được gọi là tìm kiếm một nửa là thụât toán tiếp kiếm được sử dụng cực kì nhiều trên thực tế cho phép tìm kiếm vị trí của một phần tử trong một mảng đã được sắp xếp.

thuat toan tim kiem tuyen tinh gif

Thụât toán tìm kiếm nhị phân thực hiện tìm kiếm một mảng đã bố trí bằng cách liên tục chia các khoảng tìm kiếm thành 1 nửa. Bắt đầu với một khoảng từ phần tử đầu mảng, tới cuối mảng. Nếu giá trị của phần tử cần tìm nhỏ hơn giá trị của phần từ nằm ở giữa khoảng thì thu hẹp phạm vi tìm kiếm từ đầu mảng tới giửa mảng và nguợc lại. Cứ thế tiếp tục chia phạm vi thành các nửa cho dến khi tìm thấy hoặc đã duyệt hết.

2. Ý tưởng thụât toán

Thuật toán tìm kiếm nhi phân là một thuật toán khá thông dụng và chỉ dùng được với một mảng đã sắp đặt. Để khai triển thuật toán này hãy chắc chắn rằng mảng đã được bố trí. Sau đây là cảm hứng khai triển thuật toán.

  • Xét một đoạn trong mảng arr[left…right]. Lúc này thành quả của left và right lần luợt là 0 và số phần tử của mảng - 1.
  • So sánh x với phần tử nằm ở vị trí chủ đạo giữa của mảng (mid = (left + right) /2). Nếu như x bằng arr[mid] thì trả về vị trí và thoát vòng lặp.
  • Nếu như x < arr[mid] thì chắc chắn x sẽ nằm ở phía bên trái tức là từ arr[left….mid-1].
  • Nếu như x > arr[mid] thì chắc chắn x sẽ nằm ở phía bên phải mid tức là ở khoảng arr[mid+1…right].
  • Bắt đầu hành động chia đôi các khoảng tìm kiếm tới khi nào tìm thấy được vị trí của x trong mảng hoặc khi đã duyệt hết mảng.

3. Triển khai thụât toán

Sau đây chính là các bước khai triển thuật toán, quá trình hành động đều được bình luận ở từng đoạn.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include
using namespace std;
//Hàm tìm kiếm nhi phân
int binarySearch(int arr[], int left, int right, int x)
int middle;
while(left <= right)
// tính vị trí ở giữa left và right
middle = (left + right) / 2;
// nếu phần từ ở giữa bằng x thì trả về
// vị trí
if (arr[middle] == x)
return middle;
// nếu x lớn hơn phần tử ở giữa thì
// bảo đảm nó nằm bên phải.
// Chỉ định left phần từ ở giữa + 1
if (x > arr[middle])
left = middle + 1;
else
//Ngược lại
right = middle - 1;
//Trả về -1 nếu không tìm thấy gía trị trong mảng.
return -1;
int main()
int arr[] = 15, 20, 25, 30, 31, 44, 66;
//Lấy ra độ dài của mảng
int n = sizeof(arr) / sizeof(arr[0]);
//Phần từ cần tìm
int x = 25;
// n -1 là vị trí cuối cùng trong mảng.
int result = binarySearch(arr, 0, n-1, x);
cout << result;

Khởi chạy chương trình chúng ta sẽ nhận được kết quả là vị trí của 25 trong mảng.

1
Output : 2

>>>Xem thêm: Mã nguồn mở là gì? Tổng hợp các mã nguồn mở tốt nhất hiện nay

Ý tưởng của thuật toán tìm kiếm nhị phân

Tìm kiếm nhị phân
Tìm kiếm nhị phân

Chú ý: Trong bài đăng tôi giả sử mảng đang sắp xếp tăng dần. Với trường hợp mảng sắp xếp giảm dần, bạn đọc sau khi hiểu thuật toán sẽ có thể tự làm.

Do tính chất mảng đã sắp xếp, quá trình tìm kiếm phần tử x có thể khai triển như sau:

  1. Xét đoạn mảng arr[left…right] cần tìm kiếm phần tử x. Ta so sánh x với phần tử ở vị trí giữa của mảng(mid = (left + right)/2). Nếu:
  2. Nếu như phần tử arr[mid] = x. Kết luận và thoát chương trình.
  3. Nếu như arr[mid] < x. Chỉ tìm kiếm trên đoạn arr[mid+1…right].
  4. Nếu arr[mid] > x. Chỉ tìm kiếm trên đoạn arr[left…mid-1].

>>>Xem thêm: Những phần mềm viết Code tốt nhất cho lập trình viên hiện nay

Tóm lại

Tìm kiếm nhị phân
Tìm kiếm nhị phân

Trên đây là phần giới thiệu cũng như triển khai của thụât toán tìm kiếm nhị phân. Đây cũng là một thuật toán hay được sử dụng cũng như rât có ích trong quá trình giải các bài toán tìm kiếm.

Bài viết trên, mình đã chia sẻ tới các bạn những nội dung thiết yếu của tìm kiếm nhị phân. Cảm ơn các bạn đã theo dõi bài viết nhé!

>>Xem thêm: Source Code là gì? Tổng hợp các loại mã nguồn phổ biến nhất hiện nay

Mỹ Phượng-Tổng hợp

Tham khảo: (phattrienphanmem123az, dnmtechs,…)

Tags: Bài tập tìm kiếm nhị phândãy a phải thoả mãn:để có thể thực hiện tìm kiếm nhị phân trên dãy aĐộ phức tạp của thuật toán tìm kiếm nhị phânMô phỏng thuật toán tìm kiếm nhị phânThuật toán tìm kiếm nhị phân PascalỨng dụng thuật toán tìm kiếm nhị phânVí dụ về tìm kiếm nhị phân
Bài Viết Trước

Mã UTM code là gì? Cách đo lường hiệu quả chiến dịch quảng cáo

Bài Viết Tiếp Theo

Thuật toán sắp xếp nào là nhanh nhất?

Bài Viết Tiếp Theo
Devmastr Sort It Logo

Thuật toán sắp xếp nào là nhanh nhất?

Bài Viết Mới

Lập trình hướng đối tượng OOP là gì? 5 ngôn ngữ OOP phổ biến nhất

Lập trình hướng đối tượng OOP là gì? 5 ngôn ngữ OOP phổ biến nhất

02/02/2023
Tại sao Python phổ biến trong giới công nghệ hiện nay

Tại sao Python phổ biến trong giới công nghệ hiện nay

23/01/2023

OpenCv là gì? Mã nguồn mở OpenCV đem lại những ích lợi gì?

18/01/2023
Blockchain là gì? Ưu điểm của Blockchain trong cuộc sống

Blockchain là gì? Ưu điểm của Blockchain trong cuộc sống

08/01/2023
8 phần mềm chỉnh sửa ảnh miễn phí tốt nhất hiện nay

8 phần mềm chỉnh sửa ảnh miễn phí tốt nhất hiện nay

03/01/2023
10 phần mềm diệt virus miễn phí tốt nhất hiện nay

10 phần mềm diệt virus miễn phí tốt nhất hiện nay

29/12/2022

Về Chúng Tôi

Source.vn là website download source code free website, phần mềm, đồ án môn học, luận văn tốt nghiệp, tổng hợp các mã nguồn, kiến thức lập trình chuyên nghành công nghệ thông tin.

Chuyên Mục

  • Chưa được phân loại
  • Kiến Thức
  • Source miễn phí
  • Source Tham Khảo
  • Thư Viện
  • Top Source

Bài Viết Mới

  • Lập trình hướng đối tượng OOP là gì? 5 ngôn ngữ OOP phổ biến nhất
  • Tại sao Python phổ biến trong giới công nghệ hiện nay
  • OpenCv là gì? Mã nguồn mở OpenCV đem lại những ích lợi gì?
  • Trang Chủ
  • Top Source
  • Source miễn phí
  • Source Tham Khảo
  • Kiến Thức
  • Thư Viện

© 2023 JNews - Premium WordPress news & magazine theme by Jegtheme.