Một danh sách được liên kết đơn lẻ là một danh sách được liên kết (cấu trúc dữ liệu lưu trữ giá trị của một nút và vị trí bộ nhớ của nút tiếp theo) chỉ có thể đi theo một chiều.
Tìm kiếm nhị phân là một thuật toán tìm kiếm dựa trên phép chia và phép tắc. Điều đó tìm thấy phần tử ở giữa của cấu trúc và so sánh và sử dụng các lệnh gọi đệ quy cho cùng một thuật toán cho bất đẳng thức.
Ở đây, chúng tôi được cung cấp một danh sách được liên kết riêng và một phần tử được tìm thấy bằng cách sử dụng tìm kiếm nhị phân.
Vì danh sách liên kết đơn là cấu trúc dữ liệu chỉ sử dụng một con trỏ, nên không dễ dàng tìm thấy phần tử ở giữa của nó. Đến giữa danh sách được liên kết đơn lẻ, chúng tôi sử dụng hai cách tiếp cận con trỏ.
THUẬT TOÁN
Step 1 : Initialize, start_node (head of list) and last_node (will have last value) , mid_node (middle node of the structure). Step 2 : Compare mid_node to element Step 2.1 : if mid_node = element, return value “found”. Step 2.2 : if mid_node > element, call binary search on lower_Half. Step 2.3 : if mid_node < element, call binary search on upper_Half. Step 3 : if entire list is traversed, return “Not found”.
Ví dụ
#include<stdio.h>
#include<stdlib.h>
struct Node{
int data;
struct Node* next;
};
Node *newNode(int x){
struct Node* temp = new Node;
temp->data = x;
temp->next = NULL;
return temp;
}
struct Node* mid_node(Node* start, Node* last){
if (start == NULL)
return NULL;
struct Node* slow = start;
struct Node* fast = start -> next;
while (fast != last){
fast = fast -> next;
if (fast != last){
slow = slow -> next;
fast = fast -> next;
}
}
return slow;
}
struct Node* binarySearch(Node *head, int value){
struct Node* start = head;
struct Node* last = NULL;
do{
Node* mid = mid_node(start, last);
if (mid == NULL)
return NULL;
if (mid -> data == value)
return mid;
else if (mid -> data < value)
start = mid -> next;
else
last = mid;
}
while (last == NULL || last != start);
return NULL;
}
int main(){
Node *head = newNode(54);
head->next = newNode(12);
head->next->next = newNode(18);
head->next->next->next = newNode(23);
head->next->next->next->next = newNode(52);
head->next->next->next->next->next = newNode(76);
int value = 52;
if (binarySearch(head, value) == NULL)
printf("Value is not present in linked list\n");
else
printf("The value is present in linked list\n");
return 0;
} Đầu ra
The value is present in linked list