Binary Search in C++

Using Binary Search on Linked Lists

Can binary search be used on linked lists, and if so, how?

Abstract art representing computer programming

Binary search cannot be efficiently applied to linked lists because it requires random access to the elements.

Linked lists only support sequential access, which means you can't directly jump to the middle element like you can with arrays or vectors.

However, you can still perform a search on a linked list, but it won't be as efficient as binary search.

Why Binary Search Doesn't Work on Linked Lists

Binary search works by dividing the search space in half repeatedly, which requires O(1)O(1) time access to the middle element.

Linked lists, however, have O(n)O(n) time access to elements, as you must traverse from the head node to reach any specific element.

Alternative: Linear Search

For linked lists, a linear search is more suitable. Here’s an example of performing a linear search on a singly linked list:

#include <iostream>

// Define a node in the linked list
struct Node {
  int data;
  Node* next;
};

// Function to search for a value in the linked list
bool linearSearch(Node* head, int target) {
  Node* current = head;
  while (current != nullptr) {
    if (current->data == target) {
      return true;
    }
    current = current->next;
  }
  return false;
}

int main() {
  // Create a linked list: 1 -> 2 -> 3 -> 4 -> 5
  Node n1{1, nullptr},
    n2{2, nullptr},
    n3{3, nullptr},
    n4{4, nullptr},
    n5{5, nullptr};

  n1.next = &n2;
  n2.next = &n3;
  n3.next = &n4;
  n4.next = &n5;

  int target = 3;
  bool found = linearSearch(&n1, target);

  std::cout << "The number " << target
    << (found ? " was" : " was not") << " found";
}
The number 3 was found

Optimizing Search in Linked Lists

If you need faster search capabilities, consider these alternatives:

  1. Convert to Array: Copy the linked list elements to an array, sort the array, and then perform binary search.
  2. Skip List: A skip list is a layered linked list that allows faster search by skipping over nodes, achieving O(logn)O(log n) time complexity for search operations.
  3. Binary Search Tree (BST): Convert your linked list to a BST for efficient searching.

Example of Converting Linked List to Array

Here’s a simple example to convert a linked list to an array and then perform a binary search:

#include <algorithm>
#include <iostream>
#include <vector>

struct Node {
  int data;
  Node* next;
};

std::vector<int> linkedListToArray(Node* head) {
  std::vector<int> arr;
  Node* current = head;
  while (current != nullptr) {
    arr.push_back(current->data);
    current = current->next;
  }
  return arr;
}

int main() {
  Node n1{1, nullptr},
    n2{2, nullptr},
    n3{3, nullptr},
    n4{4, nullptr},
    n5{5, nullptr};

  n1.next = &n2;
  n2.next = &n3;
  n3.next = &n4;
  n4.next = &n5;

  std::vector<int> array = linkedListToArray(&n1);
  std::sort(array.begin(), array.end());

  bool found = std::binary_search(
    array.begin(), array.end(), 3);

  std::cout << "The number 3 "
    << (found ? "was" : "was not") << " found";
}
The number 3 was found

While binary search is not suitable for linked lists due to their sequential access nature, you can use linear search or consider alternative data structures to achieve efficient searching.

This Question is from the Lesson:

Binary Search in C++

An introduction to the advantages of binary search, and how to use it with the C++ standard library algorithms binary_search(), lower_bound(), upper_bound(), and equal_range()

Answers to questions are automatically generated and may not have been reviewed.

This Question is from the Lesson:

Binary Search in C++

An introduction to the advantages of binary search, and how to use it with the C++ standard library algorithms binary_search(), lower_bound(), upper_bound(), and equal_range()

A computer programmer
Part of the course:

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Free, unlimited access

This course includes:

  • 124 Lessons
  • 550+ Code Samples
  • 96% Positive Reviews
  • Regularly Updated
  • Help and FAQ
Free, Unlimited Access

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Screenshot from Warhammer: Total War
Screenshot from Tomb Raider
Screenshot from Jedi: Fallen Order
Contact|Privacy Policy|Terms of Use
Copyright © 2024 - All Rights Reserved