Defitnion linkConsider a Boolean function (predicate) $$ f : {0,1,\dots, n-1} \to {0, 1} $$ which is non‑decreasing: $$ f(0) \leq f(1) \leq \dots \leq f(n-1) $$ Because the values never switch back from $1$ to $0$, there is at most one $``jump’’$ from $0$ to $1$. Binary search can exploit this property to locate that jump without evaluating $f$ at every index: It seeks the largest index $L$ with $f(L)=0$ and the smallest index $R=L+1$ with $f(R)=1$ (when such indices exist). If the array is all zeros, binary search reports $L=n−1$. If the array is all ones, it reports $L=−1$. Example 1: Lower Bound 12 linkThe example shows a binary search that locates the first element in a sorted vector that is $\geq 12$: The Code link C++ Java class BinarySearch { private: bool pred(const int num) { if (num >= 12) return true; return false; } public: int search(const vector &nums) { int n = int(nums.size()); int low = -1; int high = n; while (high > low + 1) { int mid = low + (high - low) / 2; if (pred(nums[mid])) { high = mid; } else { low = mid; } } return high; } }; static boolean pred(int num) { if (num >= 12) return true; return false; } static int search(int[] nums) { int low = -1; int high = nums.length; while (high > low + 1) { int mid = low + (high - low) / 2; if (pred(nums[mid])) { high = mid; } else { low = mid; } } return high; } Running link C++ Java int main() { vector nums = {2, 4, 9, 12, 12, 12, 43, 78, 85, 89}; BinarySearch binarySearch; cout << binarySearch.search(nums) << endl; } public static void main(String[] args) { int[] nums = {2, 4, 9, 12, 12, 12, 43, 78, 85, 89}; int key = 12; System.out.println(search(nums, key)); } The output should be: 3 Code on GitHub linkSee the implementation code. Example 2: Rightmost 12 linkThe example shows a binary search that returns the index of the last element strictly less than 12 in a sorted vector (yielding $n − 1$ if every element is $<12$ and $‑1$ if none are). The Code link C++ Java class BinarySearch { private: bool pred(const int num) { if (num >= 12) return true; return false; } public: int search(const vector &nums) { int n = int(nums.size()); int low = -1; int high = n; while (high > low + 1) { int mid = low + (high - low) / 2; if (pred(nums[mid])) { high = mid; } else { low = mid; } } return low; } }; static boolean pred(int num) { if (num >= 12) return true; return false; } static int search(int[] nums) { int low = -1; int high = nums.length; while (high > low + 1) { int mid = low + (high - low) / 2; if (pred(nums[mid])) { high = mid; } else { low = mid; } } return low; } Running link C++ Java int main() { vector nums = {2, 4, 9, 12, 12, 12, 43, 78, 85, 89}; BinarySearch binarySearch; cout << binarySearch.search(nums) << endl; } public static void main(String[] args) { int[] nums = {2, 4, 9, 12, 12, 12, 43, 78, 85, 89}; int key = 12; System.out.println(search(nums, key)); } The output should be: 2 Code on GitHub linkSee the implementation code. Example 3: Last 12 linkThe example shows a binary search that returns the index of right‑most element that is $\leq 12$ in a sorted vector. The Code link C++ Java class BinarySearch { private: bool pred(const int num) { if (num > 12) return true; return false; } public: int search(const vector &nums) { int n = int(nums.size()); int low = -1; int high = n; while (high > low + 1) { int mid = low + (high - low) / 2; if (pred(nums[mid])) { high = mid; } else { low = mid; } } return low; } }; static boolean pred(int num) { if (num > 12) return true; return false; } static int search(int[] nums) { int low = -1; int high = nums.length; while (high > low + 1) { int mid = low + (high - low) / 2; if (pred(nums[mid])) { high = mid; } else { low = mid; } } return low; } Running link C++ Java int main() { vector nums = {2, 4, 9, 12, 12, 12, 43, 78, 85, 89}; BinarySearch binarySearch; cout << binarySearch.search(nums) << endl; } public static void main(String[] args) { int[] nums = {2, 4, 9, 12, 12, 12, 43, 78, 85, 89}; int key = 12; System.out.println(search(nums, key)); } The output should be: 5 Code on GitHub linkSee the implementation code.

Greedy Algorithms