Binary Search

Binary search: the ultimate solution to finding what you're looking for in a hurry. Don't waste your time with those slow linear searches - binary search is where it's at.

But how does it work, you ask? Well, it's simple. Just follow these easy steps:

1. First, you need a sorted list of items. It doesn't matter what the items are - numbers, words, memes, it's all good.
2. Next, pick a random item from the list and compare it to the thing you're looking for. If it's the same, great! You found it. If not, move on to step 3.
3. Determine whether the item you're looking for is greater than or less than the item you just picked. If it's greater, search the upper half of the list. If it's less, search the lower half.
4. Repeat steps 2 and 3 until you find the item you're looking for, or until you realize that it's not in the list. In which case, maybe try a linear search. Just kidding, linear search is the worst.

Okay, now that you know the basic idea, let's see some code. Here's how you might implement binary search in C++:

#include <iostream>
#include <vector>

int binarySearch(const std::vector<int>& list, int item)
{
    int low = 0;
    int high = list.size() - 1;
    int mid;

    while (low <= high)
    {
        mid = (low + high) / 2;
        if (list[mid] == item)
        {
            return mid;
        }
        else if (item < list[mid])
        {
            high = mid - 1;
        }
        else
        {
            low = mid + 1;
        }
    }

    return -1; // item not found
}

int main()
{
    std::vector<int> list = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int item = 5;
    int index = binarySearch(list, item);

    if (index >= 0)
    {
        std::cout << "Found " << item << " at index " << index << std::endl;
    }
    else
    {
        std::cout << "Could not find " << item << " in list" << std::endl;
    }