Defitnion

Consider 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

The example shows a binary search that locates the first element in a sorted vector that is $\geq 12$:

The Code 

  class BinarySearch {
private:
    bool pred(const int num) {
        if (num >= 12) return true;
        return false;
    }

public:
    int search(const vector<int> &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 

  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

See the implementation code.

 

Example 2: Rightmost 12

The 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 

  class BinarySearch {
private:
    bool pred(const int num) {
        if (num >= 12) return true;
        return false;
    }

public:
    int search(const vector<int> &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 

  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

See the implementation code.

 

Example 3: Last 12

The example shows a binary search that returns the index of right‑most element that is $\leq 12$ in a sorted vector.

The Code 

  class BinarySearch {
private:
    bool pred(const int num) {
        if (num > 12) return true;
        return false;
    }

public:
    int search(const vector<int> &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 

  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

See the implementation code.

Last updated 11 May 2025, 18:45 +0500 . history