# Binary Search

<details>

<summary>search index of item <mark style="color:orange;">exactly equal</mark> to given number (if repeated, then <mark style="color:green;">first occurrence</mark>)</summary>

```
// **************** Own Implementation ****************

int binarySearch(vector<int>& arr, int low, int high, int target) {
    if (low == high) {
        if(arr[low] == target){
            return low;
        } else {
            return -1;
        }
    } 

    int mid = (low + high) / 2;

    if (arr[mid] < target) {
        return binarySearch(arr, mid + 1, high, target);
    } else {
        return binarySearch(arr, low, mid, target);
    }
}


int binarySearch(vector<int>& arr, int target) {
    if (arr.empty()) {
        return -1;
    }
    return binarySearch(arr, 0, arr.size() - 1, target);
}





// ******************** Using STL **********************
#include <algorithm>

int binarySearch(vector<int>& arr, int target) {
    auto it = lower_bound(arr.begin(), arr.end(), target);
    if (it != arr.end() && *it == target) {
        return it - arr.begin();
    }
    return -1;
}

```

</details>

<details>

<summary>search index of item <mark style="color:orange;">exactly equal</mark> to given number (if repeated, then <mark style="color:green;">last occurrence</mark>)</summary>

```
// **************** Own Implementation ****************

int binarySearch(vector<int>& arr, int low, int high, int target) {
    if (low == high) {
        if(arr[low] == target){
            return low;
        } else {
            return -1;
        }
    } 

    int mid = (low + high + 1) / 2;

    if (target < arr[mid]) {
        return binarySearch(arr, low, mid-1, target);
    } else {
        return binarySearch(arr, mid, high, target);
    }
}


int binarySearch(vector<int>& arr, int target) {
    if (arr.empty()) {
        return -1;
    }
    return binarySearch(arr, 0, arr.size() - 1, target);
}



// ******************** Using STL **********************
#include <algorithm>

int binarySearch(vector<int>& arr, int target) {
    // upper_bound returns an iterator to the first element
    // that is strictly greater than 'target'
    auto it = upper_bound(arr.begin(), arr.end(), target);

    if(it == arr.begin()){
        // the first element is strictly greater than 'target'
        return -1;
    }

    // Go one step back
    it--;

    if (*it == target) {
        return it - arr.begin();
    } else {
        return -1;
    }
}

```

</details>

<details>

<summary>search index of item <mark style="color:orange;">exactly equal</mark> to given number (if repeated, then <mark style="color:green;">any occurrence</mark>)</summary>

<pre><code>// **************** Own Implementation ****************


<strong>int binarySearch(vector&#x3C;int>&#x26; arr, int low, int high, int target) {
</strong>    if (low > high) {
        return -1;
    }

    int mid = (low + high) / 2;

    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] &#x3C; target) {
        return binarySearch(arr, mid + 1, high, target);
    } else {
        return binarySearch(arr, low, mid - 1, target);
    }
}


int binarySearch(vector&#x3C;int>&#x26; arr, int target) {
    if (arr.empty()) {
        return -1;
    }
    return binarySearch(arr, 0, arr.size() - 1, target);
}



// ******************** Using STL **********************
#include &#x3C;algorithm>

int binarySearch(vector&#x3C;int>&#x26; arr, int target) {
    auto it = lower_bound(arr.begin(), arr.end(), target);
    if (it != arr.end() &#x26;&#x26; *it == target) {
        return it - arr.begin();
    }
    return -1;
}

</code></pre>

</details>

<details>

<summary>search index of first item just <mark style="color:orange;">greater_than_or_equal</mark> to given number</summary>

```
// **************** Own Implementation ****************

int binarySearchGte(vector<int>& arr, int low, int high, int target) {
    if (low == high) {
        return low;
    }

    int mid = low + (high - low) / 2;

    if (target <= arr[mid]) {
        return binarySearchGte(arr, low, mid, target);
    } else {
        return binarySearchGte(arr, mid + 1, high, target);
    }
}

int binarySearchGte(vector<int>& arr, int target) {
    // assuming arr[N] contains infinity, answer is going be one of [0,N]
    return binarySearchGte(arr, 0, arr.size(), target);
}



// ******************** Using STL **********************
#include <algorithm>

int binarySearchGte(vector<int>& arr, int target) {
    auto it = lower_bound(arr.begin(), arr.end(), target);
    
    if (it == arr.end()) {
       // return arr.size() if no such element is found
       // or -1 if you prefer to indicate 'not found'.
       return arr.size();
    }
 
    return it - arr.begin();
}
```

</details>

<details>

<summary>search index of first item <mark style="color:orange;">strictly_greater_than</mark> given number</summary>

```
// **************** Own Implementation ****************

int binarySearchGreater(vector<int>& arr, int low, int high, int target) {
    if (low == high) {
        return low;
    }

    int mid = low + (high - low) / 2;

    if (target < arr[mid]) {
        return binarySearchGreater(arr, low, mid, target);
    } else {
       return binarySearchGreater(arr, mid + 1, high, target);
    }
}

int binarySearchGreater(vector<int>& arr, int target) {
    // assuming arr[N] contains infinity, answer is going be one of [0,N]
    return binarySearchGreater(arr, 0, arr.size(), target);
}



// ******************** Using STL **********************
#include <algorithm>

int binarySearchGreater(vector<int>& arr, int target) {
    auto it = upper_bound(arr.begin(), arr.end(), target);
    return it - arr.begin();
}


```

</details>

<details>

<summary>search index of last item which is <mark style="color:orange;">less_than_or_equal</mark> to given number</summary>

```
// **************** Own Implementation ****************

int binarySearchLte(vector<int>& arr, int low, int high, int target) {
    if (low == high) {
        return low;
    }

    int mid = (low + high + 1) / 2;

    if (arr[mid] <= target) {
        return binarySearchLte(arr, mid, high, target);
    } else {
        return binarySearchLte(arr, low, mid-1, target);
    }
}

int binarySearchLte(vector<int>& arr, int target) {
    // assuming arr[-1] contains -infinity, answer is going be one of [-1,N-1]
    return binarySearchLte(arr, -1, arr.size()-1, target);
}



// ******************** Using STL **********************
#include <algorithm>

int binarySearchLte(vector<int>& arr, int target) {
    // Find the first element strictly greater than 'target'.
    auto it = upper_bound(arr.begin(), arr.end(), target);

    // If 'it' is at the beginning, it means all elements in the vector
    // are strictly greater than 'target'
    if (it == arr.begin()) {
        return -1; // No element <= target found.
    }

    // If 'it' is not at the beginning, then the element immediately before it
    // is the last element less than or equal to 'target'.
    it--;
    return it - arr.begin();
}


```

</details>

<details>

<summary>search index of last item which is <mark style="color:orange;">strictly_lesser_than</mark> given number</summary>

```
// **************** Own Implementation ****************

int binarySearchLesser(vector<int>& arr, int low, int high, int target) {
    if (low == high) {
        return low;
    }

    int mid = (low + high + 1) / 2;

    if (arr[mid] < target) {
        return binarySearchLesser(arr, mid, high, target);
    } else {
        return binarySearchLesser(arr, low, mid-1, target);
    }
}

int binarySearchLesser(vector<int>& arr, int target) {
    // assuming arr[-1] contains -infinity, answer is going be one of [-1,N-1]
    return binarySearchLesser(arr, -1, arr.size()-1, target);
}



// ******************** Using STL **********************
#include <algorithm>

int binarySearchLesser(vector<int>& arr, int target) {
    // lower_bound finds the first element >= target.
    auto it = lower_bound(arr.begin(), arr.end(), target);

    // If 'it' is the beginning of the array, it means all elements are >= target,
    // or the array is empty
    if (it == arr.begin()) {
        return -1; // No element is strictly less than the target
    }

    // Decrement the iterator to point to the element immediately before
    // the first element greater than or equal to 'target'. This will be the
    // last element strictly less than 'target'.
    it--;

    return it - arr.begin();
}
```

</details>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://blog.gomchik.com/tech/c++/binary-search.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.