TÌM KIẾM NHỊ PHÂN C++

1. Thuật toán kiếm tìm kiếm nhị phân

Tìm tìm nhị phân được vận dụng trên các danh sách đang được thu xếp theo sản phẩm tự. Giả sử, tất cả mảng a0,a1,a2,..,an-1 đã được thu xếp theo đồ vật tự tăng dần. Các thành phần trong dãy gồm mối quan tiền hệ: ai -1 ≤ ai ≤ ai+1.

Bạn đang xem: Tìm kiếm nhị phân c++

Ý tưởng thuật toánNếu x > ai thì x chỉ rất có thể xuất hiện trong đoạn .Nếu x i thì x chỉ có thể xuất hiện nay trong đoạn .Tại từng bước, ta đối chiếu x với thành phần đứng thân trong mảng sẽ tìm kiếm, dựa vào kết quả so sánh này nhưng mà ta quyết định giới hạn hàng tìm kiếm ở nữa dưới hay nữa bên trên của hàng tìm kiếm hiện nay hành.Các bước tiến hành thuật toánGiả sử mảng tìm kiếm kiếm hiện tại hành bao gồm các thành phần nằm trong aleft, aright. Công việc của lời giải như sau:Bước 1: Gán left=0; right=n-1;Bước 2:mid=(left+right)/2;//chỉ số bộ phận giữa mảng hiện tại hànhSo sánh a cùng với x. Bao gồm 3 khả năng:a == x -> kiếm tìm thấy -> Dừng.a > x thì gán right=mid-1;//tìm tiếp x trong mảng nhỏ a,..,aa Bước 3: giả dụ left Minh họa thuật toánTìm x=4 vào mảng đã được thu xếp tăng dần mặt dưới.

Xem thêm: Các Loại Phương Tiện Giao Thông Đường Bộ, 20000+ Phương Tiện Giao Thông & Ảnh Ô Tô Miễn Phí

Giá trị x=4 bé dại hơn a=6 nên right=mid-1=2, left vẫn luôn là 0. Mảng nhỏ đang xét bây chừ là a,…,a.


Đánh giá thuật toán tra cứu kiếm nhị phân

Trường hợp	Số lần so sánh	Giải thích
Tốt nhất	1	Phần tử giữa của mảng có mức giá trị x
Xấu nhất	log2n	Không có x trong mảng
Trung bình	log2(n/2)	Xác suất các phần tử trong mảng nhận quý hiếm x là như nhau

Độ phức hợp của thuật toán là O(log2n).

Xem thêm: Phim Hài Những Thiên Thần Nhanh Nhạy Tập 10 Cùng Trấn Thành, Những Thiên Thần Nhanh Nhạy

Cài đặt thuật toán tra cứu kiếm nhị phân với C++Hàm BinarySearch() trả về mid là địa điểm của x trong mảng giả dụ tìm thấy x, trái lại hàm trả về giá trị -1.int BinarySearch(int a<>,int n,int x){int left, right, mid; left=0; right=n-1;do{mid=(left+right)/2;if(a==x)return mid;else if(a

2. Thiết lập thuật toán search kiếm nhị phân dùng đệ quy

Dễ thấy, thuật toán search kiếm nhị phân là việc lặp đi tái diễn của thừa trình xác định mid và so sánh a có bởi giá trị x buộc phải tìm vào mảng tuyệt không. Ta hoàn toàn có thể viết một hàm làm nhiệm vụ đó rồi call lại bao gồm nó để setup thuật toán. Đó chính là kỹ thuật lập trình đệ quy đang học sinh hoạt môn Nhập môn lập trình.int BinarySearch_Recursive(int a<>,int x,int left,int right){if(left>right)return -1;int mid=(left+right)/2;if(x==a)return mid;if(x

3. Phân tích cùng so sánh những thuật toán tìm kiếm

Sau khi tìm hiểu thuật toán search kiếm con đường tính với tìm tìm nhị phân (binary search), họ có một vài phân tích sau:– Thuật toán binary search tiết kiệm thời gian hơn tương đối nhiều so với kiếm tìm kiếm đường tính.– Thuật toán binary tìm kiếm chỉ được vận dụng cho đầy đủ mảng đã được bố trí thứ tự. Thuật toán tìm kiếm kiếm tuyến đường tính vận dụng cho bất kỳ mảng nào cũng được.– Khi sử dụng thuật toán binary tìm kiếm cần tính mang đến chi phí tổn sắp xếp. Khi mảng gồm sự biến đổi các bộ phận như thêm, xóa,… thì phải bố trí lại. Đây là khuyết điểm chính của thuật toán binary search.
Bài trước và bài sau vào môn học>" data-wpel-link="internal">Thuật toán thu xếp đổi chổ trực tiếp (Interchange Sort) >>