Tìm kiếm nhị phân là một thuật toán tìm kiếm được sử dụng để tìm vị trí của một phần tử (giá trị đích) trong một mảng được sắp xếp. Mảng phải được sắp xếp trước khi áp dụng tìm kiếm nhị phân.
Tìm kiếm nhị phân còn được gọi bằng những cái tên này, tìm kiếm logarit, tìm kiếm nhị phân, tìm kiếm nửa khoảng.
Đang làm việc
Thuật toán tìm kiếm nhị phân hoạt động bằng cách so sánh phần tử được tìm kiếm với phần tử ở giữa của mảng và dựa trên sự so sánh này theo quy trình bắt buộc.
Trường hợp 1 - element =middle, phần tử được tìm thấy trả về chỉ mục.
Trường hợp 2 - element> middle, tìm kiếm phần tử trong mảng con bắt đầu từ giữa + 1 index đến n.
Trường hợp 3 - element
Thông số inital_value, end_value Việc triển khai hàm thuật toán tìm kiếm nhị phân sử dụng lệnh gọi hàm lặp đi lặp lại. Cuộc gọi này có thể có hai loại -
Cuộc gọi lặp đi lặp lại đang lặp lại trên cùng một khối mã nhiều lần]
Cuộc gọi đệ quy đang gọi đi gọi lại cùng một hàm. THUẬT TOÁN
Step 1 : Find the middle element of array. using ,
middle = initial_value + end_value / 2 ;
Step 2 : If middle = element, return ‘element found’ and index.
Step 3 : if middle > element, call the function with end_value = middle - 1 .
Step 4 : if middle < element, call the function with start_value = middle + 1 .
Step 5 : exit.
CHƯƠNG TRÌNH THỰC HIỆN TÌM KIẾM BINARY DÙNG CUỘC GỌI ITERATIVE
Ví dụ
#include <stdio.h>
int iterativeBinarySearch(int array[], int start_index, int end_index, int element){
while (start_index <= end_index){
int middle = start_index + (end_index- start_index )/2;
if (array[middle] == element)
return middle;
if (array[middle] < element)
start_index = middle + 1;
else
end_index = middle - 1;
}
return -1;
}
int main(void){
int array[] = {1, 4, 7, 9, 16, 56, 70};
int n = 7;
int element = 16;
int found_index = iterativeBinarySearch(array, 0, n-1, element);
if(found_index == -1 ) {
printf("Element not found in the array ");
}
else {
printf("Element found at index : %d",found_index);
}
return 0;
} Đầu ra
Element found at index : 4
CHƯƠNG TRÌNH THỰC HIỆN TÌM KIẾM BINARY DÙNG NHẬN CUỘC GỌI
Ví dụ
#include <stdio.h>
int recursiveBinarySearch(int array[], int start_index, int end_index, int element){
if (end_index >= start_index){
int middle = start_index + (end_index - start_index )/2;
if (array[middle] == element)
return middle;
if (array[middle] > element)
return recursiveBinarySearch(array, start_index, middle-1, element);
return recursiveBinarySearch(array, middle+1, end_index, element);
}
return -1;
}
int main(void){
int array[] = {1, 4, 7, 9, 16, 56, 70};
int n = 7;
int element = 9;
int found_index = recursiveBinarySearch(array, 0, n-1, element);
if(found_index == -1 ) {
printf("Element not found in the array ");
}
else {
printf("Element found at index : %d",found_index);
}
return 0;
} Đầu ra
Element found at index : 3