資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
安卓
Python
C 程式設計
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 C++ 中針對單向連結串列執行二分搜尋
**單向連結串列**是一種連結串列（一種儲存節點值和下一個節點的記憶體位置的資料結構），只能單向移動。
**二分搜尋**是一種基於分治的搜尋演算法。該演算法會找到結構的中間元素，然後使用遞迴呼叫相同演算法來進行比較並判斷是否相等。
在此，我們給定一個單向連結串列和一個元素，並使用二分搜尋查詢該元素。
由於單向連結串列是一種僅使用一個指標的資料結構，因此很難找到其中間元素。若要找到單向連結串列的中間元素，我們使用兩個指標方法。
演算法
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”.
示例
#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;
}輸出
The value is present in linked list
更新於： 03-Jan-2020
2K+ 次瀏覽
廣告