Search api in c++

binary_search

Determines whether a given value exists within a sorted range. It returns a boolean value (true if the element is found, false otherwise). Please note; the input range must be sorted.

int main() {
  vector<int> nums = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
  int target = 23;
  bool ans = binary_search(nums.begin(), nums.end(), target);
  return 0;
}

lower_bound

It does find the lower bound of an element in a sorted container, it doesn't guarantee that the element itself will be found.

Here’s a breakdown of the behavior:

• Element exists: If the target element is present in the container, lower_bound will return an iterator pointing to the first occurrence of the element.
• Element doesn’t exist: If the target element is not present in the container, lower_bound will return an iterator pointing to the first position where the element could be inserted without violating the container's order.

To determine if the target element was actually found, you need to check if the iterator returned by lower_bound points to a valid element in the container and if the value at that position is equal to the target.

int main() {
  vector<int> nums = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
  int target = 23;
  auto iterator = lower_bound(nums.begin(), nums.end(), target);
  if(iterator != nums.end() && *iterator== target) {
    int index = distance(nums.begin(), iterator);
    cout << "Target found at index " << index << endl; // print 5
  } else {
    cout << "Target not found" << endl;
  }
  return 0;
}

upper_bound

Returns an iterator pointing to the first element in the range that is greater than the target value.

int main() {
  vector<int> nums = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
  int target = 23;
  auto iterator = upper_bound(nums.begin(), nums.end(), target);
  if(iterator != nums.end()) {
    int index = distance(nums.begin(), iterator);
    cout << "Upper found at index " << index << endl; // print 6
  } else {
    cout << "Target is greater than all elements" << endl;
  }
  return 0;
}

Unlike lower_bound, upper_bound does not guarantee that it will find an equal target. It will find the position where the element could be inserted if it were greater than all existing elements equal to the target.

equal_range

The equal_range is used to find the range of elements in a sorted container that are equal to a given value. It returns a pair of iterators, where the first iterator points to the beginning of the range and the second iterator points to one past the end of the range.

Following is code example for reference.

int main() {
    vector<int> numbers = {1, 3, 3, 5, 7, 7, 9};
    int target = 3;

    // Find the equal range of the target element
    auto range = equal_range(numbers.begin(), numbers.end(), target);

    // Check if elements exist
    if (range.first != range.second) {
        cout << "Elements found in the range: ";
        for (auto it = range.first; it != range.second; ++it) {
            std::cout << *it << " ";
        }
        std::cout << std::endl;
    } else {
        std::cout << "Element not found." << std::endl;
    }
    return 0;
}

partition_point

It finds the first element in a sorted range that is greater than a given value. It provides a convenient way to partition a range based on a predicate.

It requires a predicate function to determine whether an element should be placed in the first or second partition. The predicate function takes an element as input and returns a boolean value.

Without a predicate, partition_point would have no way to determine how to divide the elements.

Following is the code example.

int main() {
    vector<int> numbers = {1, 3, 5, 7, 9};
    int target = 6;

    // Find the partition point
    auto it = partition_point(numbers.begin(), numbers.end(), [target](int x) { return x < target; });

    // Check if the partition point was found
    if (it != numbers.end()) {
        cout << "First element greater than " << target << " is: " << *it << endl;
    } else {
        cout << "All elements are less than or equal to " << target << endl;
    }

    return 0;
}

inplace_merge

It is used for merging two sorted ranges within a single container. It efficiently merges the elements from the two ranges, preserving the overall sorted order of the container.

1. The ranges must be sorted before calling inplace_merge.
2. It modifies the original container in-place, merging the elements from the specified ranges.
3. inplace_merge is a generic algorithm that works with any container or iterator range that supports comparison.

Following is the code example.

int main() {
    vector<int> numbers = {1, 3, 5, 7, 9, 2, 4, 6, 8};

    // Partition the vector into two sorted halves
    int mid = numbers.size() / 2;
    inplace_merge(numbers.begin(), numbers.begin() + mid, numbers.end());

    // Print the merged vector
    for (int num : numbers) {
        cout << num << " ";
    }
    // It will print 1 2 3 4 5 6 7 8 9
    cout << endl;

    return 0;
}

nth_element

It is used for reordering the elements in a range such that the nth element is at its correct position in a sorted sequence. It provides a flexible way to find and rearrange elements based on their relative order.

int main() {
    vector<int> numbers = {5, 2, 8, 1, 9};
    int n = 2; // Find the 3rd element (index 2)

    // Reorder the elements using nth_element
    nth_element(numbers.begin(), numbers.begin() + n, numbers.end());

    // Print the nth element
    cout << "The " << n + 1 << "th element is: " << numbers[n] << std::endl;
    // The 3rd element is: 5
    return 0;
}

iota

It is used for filling a range of elements with consecutive values. It provides a simple way to initialize containers or arrays with a sequence of numbers.

int main() {
    std::vector<int> numbers(5);

    // Fill the vector with consecutive values starting from 1
    std::iota(numbers.begin(), numbers.end(), 1);

    // Print the filled vector
    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

Happy learning c++.