Skip to content

Instantly share code, notes, and snippets.

@abcdabcd987
Last active May 7, 2020 08:50
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save abcdabcd987/2eebddcd249193b0cc3f to your computer and use it in GitHub Desktop.
Save abcdabcd987/2eebddcd249193b0cc3f to your computer and use it in GitHub Desktop.
#include <vector>
/**
Given an non-decreasing ordered array `arr`, search the biggest `i` that makes `arr[i] == value`.
If `i` doesn't exist, return -1
*/
int search_last_match(const std::vector<int>& arr, const int value)
{
int lef = 0, rig = static_cast<int>(arr.size());
while (rig-lef > 1)
{
const int mid = (lef+rig)/2;
if (arr[mid] <= value)
lef = mid;
else
rig = mid;
}
return arr[lef] == value ? lef : -1;
}
/**
Given an non-decreasing ordered array `arr`, search the smallest `i` that makes `arr[i] == value`.
If `i` doesn't exist, return -1
*/
int search_first_match(const std::vector<int>& arr, const int value)
{
int lef = -1, rig = static_cast<int>(arr.size())-1;
while (rig-lef > 1)
{
const int mid = (lef+rig)/2;
if (arr[mid] >= value)
rig = mid;
else
lef = mid;
}
return arr[rig] == value ? rig : -1;
}
/**
Given an non-decreasing ordered array `arr`, search the biggest `i` that makes `arr[i] < value`.
If `i` doesn't exist, return -1
*/
int search_last_less(const std::vector<int>& arr, const int value)
{
if (arr.front() >= value)
return -1;
int lef = 0, rig = static_cast<int>(arr.size());
while (rig-lef > 1)
{
const int mid = (lef+rig)/2;
if (arr[mid] < value)
lef = mid;
else
rig = mid;
}
return lef;
}
/**
Given an non-decreasing ordered array `arr`, search the smallest `i` that makes `arr[i] > value`.
If `i` doesn't exist, return -1
*/
int search_first_greater(const std::vector<int>& arr, const int value)
{
if (arr.back() <= value)
return -1;
int lef = -1, rig = static_cast<int>(arr.size())-1;
while (rig-lef > 1)
{
const int mid = (lef+rig)/2;
if (arr[mid] > value)
rig = mid;
else
lef = mid;
}
return rig;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment