Tìm kiếm nhị phân được gọi là tìm kiếm logarit là một thuật toán tìm kiếm tìm kiếm một phần tử trong một mảng được sắp xếp. Thuật toán chia một cách đệ quy mảng thành hai nửa, nếu phần tử được tìm thấy ở vị trí giữa thì trả về, nếu không hãy gọi phép chia và kiểm tra lại cho đến khi phần tử được tìm thấy.
Đang hoạt động
Thuật toán hoạt động bằng cách so sánh phần tử ở giữa của mảng đã sắp xếp với phần tử sẽ được tìm kiếm.
Nếu phần tử tìm kiếm là bằng vào phần tử giữa, sau đó trả về chỉ mục của phần tử.
Nếu phần tử tìm kiếm lớn hơn ngoài phần tử ở giữa, tìm kiếm trong mảng con bên trái tức là mảng con từ phần tử tiếp theo của phần giữa đến cuối mảng.
Nếu phần tử tìm kiếm nhỏ hơn ngoài phần tử ở giữa, tìm kiếm trong mảng con bên phải tức là mảng con từ phần tử đầu tiên đến phần tử đứng trước phần giữa của mảng.
Cú pháp
Lệnh gọi đến sắp xếp nhị phân tiêu chuẩn, cú pháp sau được sử dụng -
binary_search(start_address , end_address , element)
Tham số
start_address là địa chỉ của phần tử đầu tiên của mảng.
end_address là địa chỉ của phần tử cuối cùng của mảng.
phần tử là phần tử được tìm thấy trong mảng.
Quay lại
Nó trả về một số nguyên có giá trị bằng chỉ số của phần tử trong mảng nếu được tìm thấy khác sẽ trả về 0.
Ví dụ
#include <algorithm>
#include <iostream>
using namespace std;
void printArray(int a[], int arraysize){
for (int i = 0; i < arraysize; ++i)
cout << a[i] << " ";
}
int main(){
int arr[] = {1 , 5, 9, 7 , 3, 2 , 0 , 4};
int sizeofarr = sizeof(arr)/sizeof(arr[0]);
cout<<"The Element of array are :\n";
printArray(arr , sizeofarr);
cout<<"\nSorting Elements of array.";
sort(arr , arr+sizeofarr);
cout<<"\nSorted array is : ";
printArray(arr, sizeofarr);
cout<<"\nElement to be searched is 4";
if(binary_search(arr , arr+sizeofarr , 4))
cout<<"\nElement found ";
else
cout<<"\nElement not found";
} Đầu ra
The Element of array are : 1 5 9 7 3 2 0 4 Sorting Elements of array. Sorted array is : 0 1 2 3 4 5 7 9 Element to be searched is 4