Why Start with a Template#

Binary Search: From Beginner to Boundary-Handling Mastery covered the principles: monotonicity, loop invariants, and why binary search is correct. This article tackles a different problem — when you actually sit down in front of the screen, what should the first line be?

The code skeleton for binary search is really just one structure. Among the three variants — searching for an element, searching for the left boundary, and searching for the right boundary — the differences are so small that they come down to just one comparison operator and one return line. But it’s precisely this tiny difference that causes the most trouble: whether the interval is closed or open, whether the initial value of right is n or n - 1, whether to return left or left - 1 — get any one of these backwards, and your code either loops forever or silently returns an index that looks reasonable but is off by one.

This article first converges all three search variants into a single skeleton, then explains one by one why each of the three “fill-in-the-blank” spots is filled the way it is, and finally provides a troubleshooting checklist. The goal is concrete: from now on, whenever you encounter any binary search problem, first recite the skeleton from memory, then just modify the three blanks.

About the Code

All three templates are provided in C / C++ / JavaScript implementations. The logic is completely equivalent; switch tabs to view. All three templates uniformly adopt the left-closed, right-open interval [left, right) — only “search for an element” retains the more intuitive left-closed, right-closed form because it needs to return early. The reason for not forcing uniformity is explained at the end of the article.

Template Overview: One Skeleton, Three Blanks#

Let’s look at the skeleton first. The problem it solves is: find the position of the “first element that satisfies a condition” on [left, right).

1
/* Generic binary search skeleton: half-open interval [left, right) */
2
left = 0, right = n                  /* ① The right endpoint is n, not n - 1 */
3
while (left < right):                /* As long as there are still elements in the interval, keep bisecting */
4
    mid = left + (right - left) / 2  /* ② Overflow-safe way to compute the midpoint */
5
    if (check(a[mid])):              /* ③ The predicate — different for every problem */
6
        right = mid                  /*    mid may be the answer, keep it */
7
    else:
8
        left = mid + 1               /*    mid is definitely not the answer, exclude it */
9
return left                          /* ④ Return left, whose value lies in [0, n] */

Inside the entire loop, only three spots require thought:

Note that the second row is fixed: as long as the condition is written correctly, the actions for the true and false branches are always the same. This is the most reassuring aspect of this skeleton — you never need to re-derive “should I ±1 or not,” because there’s only one rule:

check(mid) is true → right = mid (mid could be the answer, keep it in the interval); false → left = mid + 1 (mid definitely isn’t the answer, exclude it along with itself).

Since mid always satisfies left ≤ mid < right, the two branches respectively make the right end strictly smaller and the left end strictly larger. The interval strictly shrinks every iteration, so it naturally never loops forever.

Unified Perspective: The Three Searches Are Actually the Same Problem#

If you break apart “search for an element / left boundary / right boundary,” what they all want is actually the same kind of thing — the first index that satisfies some condition — just with different conditions:

In other words, the >= version (hereafter lowerBound) and the > version (hereafter upperBound) — these two functions cover all cases — they differ by only one comparison operator. The real difference lies in the return value: the left boundary returns directly, the right boundary needs to subtract one, and searching for an element requires an extra check of “is it actually equal.”

Remember these two conversions first. The three templates that follow are all just a wrapper layered on top of them:

1
Search left boundary (first == target) = lowerBound(target)          + verify a[i] == target
2
Search right boundary (last == target) = upperBound(target) - 1      + verify a[i] == target
3
Search insertion position                 = lowerBound(target)          (no verification, return directly)

Template A: Searching for an Element#

The most familiar scenario: find an exact value in an array, return its index if found, otherwise return -1.

This one is most intuitive with a closed interval on both ends [left, right]: return return mid immediately on a hit, and if the loop ends, it means nothing was found.

1
int search(const int *a, int n, int target) {
2
    int left = 0, right = n - 1;              /* Closed interval [left, right] */
3
    while (left <= right) {                   /* Note it's <=, not <           */
4
        int mid = left + (right - left) / 2;
5
        if (a[mid] == target) return mid;     /* Hit, return directly             */
6
        if (a[mid] < target) left = mid + 1;  /* Answer is in the right half                 */
7
        else                 right = mid - 1; /* Answer is in the left half                 */
8
    }
9
    return -1;                                /* Interval is empty, not found           */
10
}

1
#include <vector>
2

3
int search(const std::vector<int>& a, int target) {
4
    int left = 0, right = static_cast<int>(a.size()) - 1;
5
    while (left <= right) {
6
        int mid = left + (right - left) / 2;
7
        if (a[mid] == target) return mid;
8
        if (a[mid] < target) left = mid + 1;
9
        else                 right = mid - 1;
10
    }
11
    return -1;
12
}

1
function search(a, target) {
2
  let left = 0;
3
  let right = a.length - 1;                    // Closed interval [left, right]
4
  while (left <= right) {                      // Note it's <=, not <
5
    const mid = left + Math.floor((right - left) / 2);
6
    if (a[mid] === target) return mid;         // Hit, return directly
7
    if (a[mid] < target) left = mid + 1;       // Answer is in the right half
8
    else right = mid - 1;                      // Answer is in the left half
9
  }
10
  return -1;
11
}

1
int search(const int *a, int n, int target) {
2
    int i = lowerBound(a, n, target);         /* First position >= target */
3
    return (i < n && a[i] == target) ? i : -1; /* Only an exact match counts as found         */
4
}

1
int search(const std::vector<int>& a, int target) {
2
    int i = lowerBound(a, target);
3
    return (i < static_cast<int>(a.size()) && a[i] == target) ? i : -1;
4
}

1
function search(a, target) {
2
  const i = lowerBound(a, target);            // First position >= target
3
  return i < a.length && a[i] === target ? i : -1;
4
}

Template B: Search for the Left Boundary (lowerBound)#

Scenario: the array contains duplicate elements, and you want the index of the first == target; or you simply want the insertion position—the position of the first >= target.

Taking nums = [1, 2, 2, 2, 3] and target = 2 as an example, what we want is index 1:

1
nums:   1  2  2  2  3
2
index:  0  1  2  3  4
3
           ^
4
      lowerBound(2) = 1

1
/* First position >= target, return value range [0, n] */
2
int lowerBound(const int *a, int n, int target) {
3
    int left = 0, right = n;                   /* Open interval [left, right)     */
4
    while (left < right) {
5
        int mid = left + (right - left) / 2;
6
        if (a[mid] >= target) right = mid;     /* mid may be the answer, keep it   */
7
        else                  left = mid + 1;  /* mid is too small, exclude it along with itself */
8
    }
9
    return left;                               /* Index of first >= target  */
10
}

1
#include <vector>
2

3
int lowerBound(const std::vector<int>& a, int target) {
4
    int left = 0, right = static_cast<int>(a.size());  /* Open interval [left, right) */
5
    while (left < right) {
6
        int mid = left + (right - left) / 2;
7
        if (a[mid] >= target) right = mid;
8
        else                  left = mid + 1;
9
    }
10
    return left;
11
}

1
function lowerBound(a, target) {
2
  let left = 0;
3
  let right = a.length;                        // Open interval [left, right)
4
  while (left < right) {
5
    const mid = left + Math.floor((right - left) / 2);
6
    if (a[mid] >= target) right = mid;         // mid may be the answer, keep it
7
    else left = mid + 1;                       // mid is too small, exclude it along with itself
8
  }
9
  return left;                                 // Index of first >= target
10
}

Tracing through it step by step, you can see how the interval shrinks down to the answer:

1
int searchLeft(const int *a, int n, int target) {
2
    int i = lowerBound(a, n, target);          /* First >= target         */
3
    return (i < n && a[i] == target) ? i : -1; /* Only counts if it exists, otherwise -1      */
4
}

1
int searchLeft(const std::vector<int>& a, int target) {
2
    int i = lowerBound(a, target);
3
    return (i < static_cast<int>(a.size()) && a[i] == target) ? i : -1;
4
}

1
function searchLeft(a, target) {
2
  const i = lowerBound(a, target);             // First >= target
3
  return i < a.length && a[i] === target ? i : -1;
4
}

Template C: Searching for the Right Boundary (upperBound)#

Scenario: you want the index of the last == target. Same array, same target = 2, but this time you want index 3.

The most reliable approach isn’t “binary search from right to left,” but rather copy Template B and change >= to >, obtaining the position of the “first > target,” then subtracting one:

1
nums:   1  2  2  2  3
2
index:  0  1  2  3  4
3
                    ^
4
      upperBound(2) = 4          (the first > 2)
5
      upperBound(2) - 1 = 3      (the last <= 2, that is, the right boundary of 2)

1
/* First position > target, return value range [0, n] */
2
int upperBound(const int *a, int n, int target) {
3
    int left = 0, right = n;
4
    while (left < right) {
5
        int mid = left + (right - left) / 2;
6
        if (a[mid] > target) right = mid;      /* Only change: >= becomes >       */
7
        else                 left = mid + 1;
8
    }
9
    return left;                               /* Index of first > target    */
10
}
11

12
int searchRight(const int *a, int n, int target) {
13
    int i = upperBound(a, n, target) - 1;      /* Last <= target        */
14
    return (i >= 0 && a[i] == target) ? i : -1;/* Only an exact match is the right boundary        */
15
}

1
#include <vector>
2

3
int upperBound(const std::vector<int>& a, int target) {
4
    int left = 0, right = static_cast<int>(a.size());
5
    while (left < right) {
6
        int mid = left + (right - left) / 2;
7
        if (a[mid] > target) right = mid;      // Only change: >= becomes >
8
        else                 left = mid + 1;
9
    }
10
    return left;
11
}
12

13
int searchRight(const std::vector<int>& a, int target) {
14
    int i = upperBound(a, target) - 1;         // Last <= target
15
    return (i >= 0 && a[i] == target) ? i : -1;
16
}

1
function upperBound(a, target) {
2
  let left = 0;
3
  let right = a.length;
4
  while (left < right) {
5
    const mid = left + Math.floor((right - left) / 2);
6
    if (a[mid] > target) right = mid;          // Only change: >= becomes >
7
    else left = mid + 1;
8
  }
9
  return left;                                 // Index of first > target
10
}
11

12
function searchRight(a, target) {
13
  const i = upperBound(a, target) - 1;         // Last <= target
14
  return i >= 0 && a[i] === target ? i : -1;
15
}

Comparison Table of the Three Templates#

Looking at the three searches side by side, the differences are immediately clear:

To summarize all three tables in one sentence: >= and > are swapped back and forth, right = mid never changes, and the return value’s -1 and verification are patched in at the end.

Take another look at how target = 2 performs in [2,2,2,2]—this is also the fastest way to decide which template to use:

Appendix: Why Left-Closed Right-Open Is Recommended for Intervals#

The easiest place to make mistakes in binary search isn’t the algorithm—it’s the definition of the interval. Once you pin down the interval, the initial value of right, the loop condition, and the return value can all be mechanically derived. The two approaches are compared below:

Left-closed right-open is recommended for three reasons:

1. The interval length is just right - left, no +1 needed. One less +1 means one less place to get backwards.
2. The empty-interval check is built into the loop condition. left == right means the interval is empty, and while (left < right)’s stopping condition naturally aligns—no need to separately think about “when is the search considered done.”
3. “The answer may not exist” has somewhere to go. The initial value of right is n, meaning “the answer may fall one cell past the end of the array”; returning n as the insertion position won’t go out of bounds. The closed-interval approach has no such position, and handling “insert at the end” requires a special case.

The reason Template A retains the closed interval is simply that once it hits, it return, so it doesn’t need the unified semantics of “the first position satisfying the condition”—the closed interval reads more straightforwardly. If you want to keep only one style in your project, just replace Template A with its lowerBound + verification version.

Troubleshooting Checklist: If You Get Binary Search Wrong, It’s Almost Always One of These Four#

1
int left = 0, right = n;      /* Open interval, ✓ */
2
int left = 0, right = n - 1;  /* Open interval, ✗ the last cell is missed */

1
int mid = (left + right) / 2;            /* ✗ left + right may overflow   */
2
int mid = left + (right - left) / 2;     /* ✓ Subtract first, then add, never overflows      */

Template Extension: Find First and Last Position of Element (LeetCode 34)#

Combining Template B and Template C gives you this classic problem—obtaining the entire range of target in one pass.

1
Input: nums = [5,7,7,8,8,10], target = 8
2
Output: [3,4]
3

4
Input: nums = [5,7,7,8,8,10], target = 6
5
Output: [-1,-1]
6

7
Input: nums = [], target = 0
8
Output: [-1,-1]

1
#include <stdlib.h>
2

3
int *searchRange(int *nums, int numsSize, int target, int *returnSize) {
4
    int *res = (int *)malloc(2 * sizeof(int));
5
    *returnSize = 2;
6

7
    int left  = lowerBound(nums, numsSize, target);       /* First >= target */
8
    int right = upperBound(nums, numsSize, target) - 1;   /* Last <= target */
9

10
    if (left < numsSize && nums[left] == target) {        /* Confirm target exists */
11
        res[0] = left;
12
        res[1] = right;
13
    } else {
14
        res[0] = -1;
15
        res[1] = -1;
16
    }
17
    return res;
18
}

1
#include <vector>
2
using namespace std;
3

4
class Solution {
5
public:
6
    vector<int> searchRange(vector<int>& nums, int target) {
7
        int left  = lowerBound(nums, target);             // First >= target
8
        int right = upperBound(nums, target) - 1;         // Last <= target
9

10
        if (left < (int)nums.size() && nums[left] == target)  // Confirm target exists
11
            return {left, right};
12
        return {-1, -1};
13
    }
14
};

1
function searchRange(nums, target) {
2
  const left = lowerBound(nums, target);          // First >= target
3
  const right = upperBound(nums, target) - 1;     // Last <= target
4

5
  if (left < nums.length && nums[left] === target) return [left, right];
6
  return [-1, -1];
7
}

Related Articles#

• Binary Search: From Beginner to Boundary Handling Mastery — principles, monotonicity, interval invariants, and more variants
• Sliding Window Core Code Template: Three Problems to Master All Substring and Subarray Problems — same philosophy of “one template converges a class of problems”
• Find the Duplicate Number: Binary Search and Fast-Slow Pointers — a classic example of binary searching on the value range rather than indices
• Array Two Pointers: The Optimization Tool from O(n²) to O(n) — another framework that reduces brute force to a linear scan