C++ provides several built-in functions for searching arrays and containers for specific values or ranges. These functions include both linear and binary search algorithms, as well as specialized algorithms for searching sorted and unsorted data.

Linear Search

The linear search algorithm is a simple sequential search that checks each element of an array or container in order until the desired value is found or the end of the array is reached. C++ provides the find() algorithm for performing linear search on a container. This algorithm takes two iterators that define the range to search, and a value to search for. If the value is found, find() returns an iterator to the first occurrence of the value in the range, otherwise it returns the end iterator.

Here is an example of using find() to search for a value in a vector:

#include <iostream>

int main() {
  int arr[] = {1, 2, 3, 4, 5};
  int n = sizeof(arr) / sizeof(arr[0]);
  int x = 3;

  int i;
  for (i = 0; i < n; i++) {
    if (arr[i] == x) {
      std::cout << "Value found: " << x << '\n';
      break;
    }
  }

  if (i == n) {
    std::cout << "Value not found\n";
  }

  return 0;
}

Output:

Found value: 3

Binary Search

The binary search algorithm is a more efficient search algorithm than linear search that only works on sorted arrays or containers. It works by repeatedly dividing the search interval in half until the desired value is found or the interval is empty. C++ provides the binary_search() algorithm for performing binary search on a container. This algorithm takes two iterators that define the sorted range to search, and a value to search for. If the value is found, binary_search() returns true, otherwise it returns false.

Here is an example of using binary_search() to search for a value in a vector:

#include <iostream>

int main() {
  int arr[] = {1, 2, 3, 4, 5};
  int n = sizeof(arr) / sizeof(arr[0]);
  int x = 3;

  int left = 0;
  int right = n - 1;
  int mid;

  while (left <= right) {
    mid = (left + right) / 2;

    if (arr[mid] == x) {
      std::cout << "Value found\n";
      break;
    } else if (arr[mid] < x) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  if (left > right) {
    std::cout << "Value not found\n";
  }

  return 0;
}

Output:

Value found

Sorted Algorithms

C++ also provides several specialized search algorithms for sorted data, including lower_bound(), upper_bound(), and equal_range(). These algorithms can be more efficient than linear or binary search when searching for a range of values in a sorted container.

The lower_bound() algorithm returns an iterator to the first element in a sorted container that is not less than a given value. The upper_bound() algorithm returns an iterator to the first element in a sorted container that is greater than a given value. The equal_range() algorithm returns a pair of iterators that define the range of elements in a sorted container that are equal to a given value.

Here is an example of using lower_bound() to find the first element in a sorted vector that is not less than a given value:

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

int main() {
  std::vector<int> v {1, 2, 3, 3, 3, 4, 5};

  auto result = std::lower_bound(v.begin(), v.end(), 3);

  std::cout << "Found value: " << *result << '\n';

  return 0;
}

Output:

Found value: 3

Interpolation Search

#include <iostream>

int main() {
  int arr[] = {1, 2, 3, 4, 5};
  int n = sizeof(arr) / sizeof(arr[0]);
  int x = 3;

  int left = 0;
  int right = n - 1;
  int pos;

  while (left <= right && x >= arr[left] && x <= arr[right]) {
    pos = left + ((x - arr[left]) * (right - left)) / (arr[right] - arr[left]);

    if (arr[pos] == x) {
      std::cout << "Value found\n";
      break;
    } else if (arr[pos] < x) {
      left = pos + 1;
    } else {
      right = pos - 1;
    }
  }

  if (left > right) {
    std::cout << "Value not found\n";
  }

  return 0;
}

Output:

Value found