.. include:: ../global.rst

.. index::
    pair: C++; Binary Search

Binary Search
==================

.. _binarySearch:

Here's something!

.. code-block:: cpp

    #include <iostream>
    #include <vector>
    using namespace std;

    int binarySearch(vector<int> &arr, int x) {
        // Giving a starting point and an ending point
        int low = 0;
        int high = arr.size() - 1;
        //Do all of this, so long as we dont find anything or end
        while (low <= high) {
            int mid = low + (high - low) / 2;

            // See if x is present at mid
            if (arr[mid] == x)
                return mid;

            // If x greater, ignore left half
            if (arr[mid] < x)
                low = mid + 1;

            // If x is smaller, ignore right half
            else
                high = mid - 1;
        }

        // If we reach here, then element was not present
        return -1;
    }

    int main() {
        vector<int> arr = { 2, 3, 4, 10, 40 };
        int x = 10;
        int result = binarySearch(arr, x);
        if(result == -1) cout << "Element is not present in array";
        else cout << "Element is present at index " << result << "\n";
        return 0;
    }

The whole point of a binary search is to search through data that's already been sorted through. If it's not already sorted, then there's really no point to it.