Using Binary Search on Linked Lists

1#include <iostream>
2
3// Define a node in the linked list
4struct Node {
5  int data;
6  Node* next;
7};
8
9// Function to search for a value in the linked list
10bool linearSearch(Node* head, int target) {
11  Node* current = head;
12  while (current != nullptr) {
13    if (current->data == target) {
14      return true;
15    }
16    current = current->next;
17  }
18  return false;
19}
20
21int main() {
22  // Create a linked list: 1 -> 2 -> 3 -> 4 -> 5
23  Node n1{1, nullptr},
24    n2{2, nullptr},
25    n3{3, nullptr},
26    n4{4, nullptr},
27    n5{5, nullptr};
28
29  n1.next = &n2;
30  n2.next = &n3;
31  n3.next = &n4;
32  n4.next = &n5;
33
34  int target = 3;
35  bool found = linearSearch(&n1, target);
36
37  std::cout << "The number " << target
38    << (found ? " was" : " was not") << " found";
39}

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5struct Node {
6  int data;
7  Node* next;
8};
9
10std::vector<int> linkedListToArray(Node* head) {
11  std::vector<int> arr;
12  Node* current = head;
13  while (current != nullptr) {
14    arr.push_back(current->data);
15    current = current->next;
16  }
17  return arr;
18}
19
20int main() {
21  Node n1{1, nullptr},
22    n2{2, nullptr},
23    n3{3, nullptr},
24    n4{4, nullptr},
25    n5{5, nullptr};
26
27  n1.next = &n2;
28  n2.next = &n3;
29  n3.next = &n4;
30  n4.next = &n5;
31
32  std::vector<int> array = linkedListToArray(&n1);
33  std::sort(array.begin(), array.end());
34
35  bool found = std::binary_search(
36    array.begin(), array.end(), 3);
37
38  std::cout << "The number 3 "
39    << (found ? "was" : "was not") << " found";
40}