Dada una lista enlazada individualmente y una clave, encuentre la clave utilizando un enfoque de búsqueda binaria .
Para realizar una búsqueda binaria basada en el algoritmo Divide and Conquer, es importante determinar el elemento central. La búsqueda binaria suele ser rápida y eficiente para arrays porque acceder al índice medio entre dos índices dados es fácil y rápido (complejidad de tiempo O (1)). Pero la asignación de memoria para la lista enlazada individualmente es dinámica y no contigua, lo que dificulta encontrar el elemento intermedio. Un enfoque podría ser el uso de skip list , uno podría estar recorriendo la lista enlazada usando un puntero.
Requisito previo: encontrar el medio de una lista enlazada.
Nota: El enfoque y la implementación que se proporcionan a continuación son para mostrar cómo se puede implementar la búsqueda binaria en una lista vinculada. La implementación toma O(n) tiempo.
Acercarse :
- Aquí, se dan el Node de inicio (establecido en Encabezado de la lista) y el último Node (establecido en NULL inicialmente).
- El medio se calcula utilizando el enfoque de dos punteros.
- Si los datos del medio coinciden con el valor requerido de búsqueda, devuélvalo.
- De lo contrario, si los datos del medio <valor, muévase a la mitad superior (configurando el inicio al siguiente del medio).
- De lo contrario, vaya a la mitad inferior (configurando el último en el medio).
- La condición para salir es que se encuentre el elemento o se recorra toda la lista. Cuando se recorre toda la lista, los últimos puntos de inicio, es decir, último -> siguiente == inicio.
En la función principal, la función InsertAtHead inserta el valor al principio de la lista enlazada. Insertar dichos valores (por simplicidad) para que la lista creada se ordene.
Ejemplos:
Input : Enter value to search : 7 Output : Found Input : Enter value to search : 12 Output : Not Found
C++
// CPP code to implement binary search
// on Singly Linked List
#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;
}
// function to find out middle element
struct Node* middle(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;
}
// Function for implementing the Binary
// Search on linked list
struct Node* binarySearch(Node *head, int value)
{
struct Node* start = head;
struct Node* last = NULL;
do
{
// Find middle
Node* mid = middle(start, last);
// If middle is empty
if (mid == NULL)
return NULL;
// If value is present at middle
if (mid -> data == value)
return mid;
// If value is more than mid
else if (mid -> data < value)
start = mid -> next;
// If the value is less than mid.
else
last = mid;
} while (last == NULL ||
last != start);
// value not present
return NULL;
}
// Driver Code
int main()
{
Node *head = newNode(1);
head->next = newNode(4);
head->next->next = newNode(7);
head->next->next->next = newNode(8);
head->next->next->next->next = newNode(9);
head->next->next->next->next->next = newNode(10);
int value = 7;
if (binarySearch(head, value) == NULL)
printf("Value not present\n");
else
printf("Present");
return 0;
}
Java
// Java code to implement binary search
// on Singly Linked List
// Node Class
class Node
{
int data;
Node next;
// Constructor to create a new node
Node(int d)
{
data = d;
next = null;
}
}
class BinarySearch
{
// function to insert a node at the beginning
// of the Singly Linked List
static Node push(Node head, int data)
{
Node newNode = new Node(data);
newNode.next = head;
head = newNode;
return head;
}
// Function to find middle element
// using Fast and Slow pointers
static Node middleNode(Node start, Node last)
{
if (start == null)
return null;
Node slow = start;
Node fast = start.next;
while (fast != last)
{
fast = fast.next;
if (fast != last)
{
slow = slow.next;
fast = fast.next;
}
}
return slow;
}
// function to insert a node at the beginning
// of the Singly Linked List
static Node binarySearch(Node head, int value)
{
Node start = head;
Node last = null;
do
{
// Find Middle
Node mid = middleNode(start, last);
// If middle is empty
if (mid == null)
return null;
// If value is present at middle
if (mid.data == value)
return mid;
// If value is less than mid
else if (mid.data > value)
{
start = mid.next;
}
// If the value is more than mid.
else
last = mid;
} while (last == null || last != start);
// value not present
return null;
}
// Driver Code
public static void main(String[] args)
{
Node head = null;
// Using push() function to
// convert singly linked list
// 10 -> 9 -> 8 -> 7 -> 4 -> 1
head = push(head, 1);
head = push(head, 4);
head = push(head, 7);
head = push(head, 8);
head = push(head, 9);
head = push(head, 10);
int value = 7;
if (binarySearch(head, value) == null)
{
System.out.println("Value not present");
}
else
{
System.out.println("Present");
}
}
}
// This code is contributed by Vivekkumar Singh
Python
# Python code to implement binary search
# on Singly Linked List
# Link list node
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
def newNode(x):
temp = Node(0)
temp.data = x
temp.next = None
return temp
# function to find out middle element
def middle(start, last):
if (start == None):
return None
slow = start
fast = start . next
while (fast != last):
fast = fast . next
if (fast != last):
slow = slow . next
fast = fast . next
return slow
# Function for implementing the Binary
# Search on linked list
def binarySearch(head,value):
start = head
last = None
while True :
# Find middle
mid = middle(start, last)
# If middle is empty
if (mid == None):
return None
# If value is present at middle
if (mid . data == value):
return mid
# If value is more than mid
elif (mid . data < value):
start = mid . next
# If the value is less than mid.
else:
last = mid
if not (last == None or last != start):
break
# value not present
return None
# Driver Code
head = newNode(1)
head.next = newNode(4)
head.next.next = newNode(7)
head.next.next.next = newNode(8)
head.next.next.next.next = newNode(9)
head.next.next.next.next.next = newNode(10)
value = 7
if (binarySearch(head, value) == None):
print("Value not present\n")
else:
print("Present")
# This code is contributed by Arnab Kundu
C#
// C# code to implement binary search
// on Singly Linked List
using System;
// Node Class
public class Node
{
public int data;
public Node next;
// Constructor to create a new node
public Node(int d)
{
data = d;
next = null;
}
}
class BinarySearch
{
// function to insert a node at the beginning
// of the Singly Linked List
static Node push(Node head, int data)
{
Node newNode = new Node(data);
newNode.next = head;
head = newNode;
return head;
}
// Function to find middle element
// using Fast and Slow pointers
static Node middleNode(Node start, Node last)
{
if (start == null)
return null;
Node slow = start;
Node fast = start.next;
while (fast != last)
{
fast = fast.next;
if (fast != last)
{
slow = slow.next;
fast = fast.next;
}
}
return slow;
}
// function to insert a node at the beginning
// of the Singly Linked List
static Node binarySearch(Node head, int value)
{
Node start = head;
Node last = null;
do
{
// Find Middle
Node mid = middleNode(start, last);
// If middle is empty
if (mid == null)
return null;
// If value is present at middle
if (mid.data == value)
return mid;
// If value is less than mid
else if (mid.data > value)
{
start = mid.next;
}
// If the value is more than mid.
else
last = mid;
} while (last == null || last != start);
// value not present
return null;
}
// Driver Code
public static void Main(String []args)
{
Node head = null;
// Using push() function to
// convert singly linked list
// 10 -> 9 -> 8 -> 7 -> 4 -> 1
head = push(head, 1);
head = push(head, 4);
head = push(head, 7);
head = push(head, 8);
head = push(head, 9);
head = push(head, 10);
int value = 7;
if (binarySearch(head, value) == null)
{
Console.WriteLine("Value not present");
}
else
{
Console.WriteLine("Present");
}
}
}
// This code is contributed by Arnab Kundu
Javascript
<script>
// JavaScript code to implement binary search
// on Singly Linked List
// Node Class
class Node
{
constructor(data)
{
this.data = data;
this.next = null;
}
}
// function to insert a node at the beginning
// of the Singly Linked List
function push(head, data)
{
var newNode = new Node(data);
newNode.next = head;
head = newNode;
return head;
}
// Function to find middle element
// using Fast and Slow pointers
function middleNode(start, last)
{
if (start == null)
return null;
var slow = start;
var fast = start.next;
while (fast != last)
{
fast = fast.next;
if (fast != last)
{
slow = slow.next;
fast = fast.next;
}
}
return slow;
}
// function to insert a node at the beginning
// of the Singly Linked List
function binarySearch(head, value)
{
var start = head;
var last = null;
do
{
// Find Middle
var mid = middleNode(start, last);
// If middle is empty
if (mid == null)
return null;
// If value is present at middle
if (mid.data == value)
return mid;
// If value is less than mid
else if (mid.data > value)
{
start = mid.next;
}
// If the value is more than mid.
else
last = mid;
} while (last == null || last != start);
// value not present
return null;
}
// Driver Code
var head = null;
// Using push() function to
// convert singly linked list
// 10 -> 9 -> 8 -> 7 -> 4 -> 1
head = push(head, 1);
head = push(head, 4);
head = push(head, 7);
head = push(head, 8);
head = push(head, 9);
head = push(head, 10);
var value = 7;
if (binarySearch(head, value) == null)
{
document.write("Value not present");
}
else
{
document.write("Present");
}
</script>
Producción:
Present
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por KunalDhyani y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA