Code Templates

Standardize your binary search implementations with these memorizable blueprints. For a deep dive into the theory, check out the Concept Guide.

The Standard Binary Search

Use this template when you need to find the exact index of an element in a sorted array with no duplicates, or when any index of the target is acceptable.

Use Case: 704. Binary Search
Time Complexity:
O(log N)
Space Complexity:
O(1)

JavaScript:

function binarySearch(nums, target) {
    let left = 0;
    let right = nums.length - 1;

    while (left <= right) {
        // Use Math.floor to handle floating point results in JS
        const mid = left + Math.floor((right - left) / 2);

        if (nums[mid] === target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

Python:

def binary_search(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1

    while left <= right:
        # // is floor division in Python
        mid = left + (right - left) // 2

        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

Java:

public int binarySearch(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

C++:

int binarySearch(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

Go:

func binarySearch(nums []int, target int) int {
    left, right := 0, len(nums)-1

    for left <= right {
        mid := left + (right-left)/2

        if nums[mid] == target {
            return mid
        } else if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    return -1
}

Ruby:

def binary_search(nums, target)
  left, right = 0, nums.length - 1

  while left <= right
    mid = left + (right - left) / 2

    if nums[mid] == target
      return mid
    elsif nums[mid] < target
      left = mid + 1
    else
      right = mid - 1
    end
  end

  -1
end

Code Breakdown

Critical Components

Pointers Initialization: left = 0, right = n - 1.
Termination Condition: while (left <= right). This ensures we check the very last element when left == right.
The Midpoint: Calculated as left + (right - left) / 2 to avoid integer overflow errors that occur with (left + right) / 2 in some languages.
The Shrinkage: Always use mid + 1 or mid - 1 to ensure the search space strictly decreases and prevents infinite loops.

State Visualization

  graph TD
    Start[Start] --> Loop{"left <= right?"}
    Loop -->|Yes| Mid[Calculate Mid]
    Mid --> Equal{"nums[mid] == target?"}
    Equal -->|Yes| Found[Return mid]
    Equal -->|No| Compare{"nums[mid] < target?"}
    Compare -->|Yes| Right[left = mid + 1]
    Compare -->|No| Left[right = mid - 1]
    Right --> Loop
    Left --> Loop
    Loop -->|No| NotFound[Return -1]

Variation: Finding Boundaries (First/Last Occurrence)

Use these when the array contains duplicates and you need a specific position.

1. Leftmost (First) Occurrence

Description: Finds the first instance of a target. Even after finding the target, it continues to search the left half.
Use Case: 34. Find First and Last Position

JavaScript:

function findFirst(nums, target) {
    let left = 0, right = nums.length - 1;
    let result = -1;
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        if (nums[mid] === target) {
            result = mid;
            right = mid - 1; // Continue searching left
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

Python:

def find_first(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    result = -1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            result = mid
            right = mid - 1
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return result

Java:

public int findFirst(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    int result = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            result = mid;
            right = mid - 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

C++:

int findFirst(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    int result = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            result = mid;
            right = mid - 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

Go:

func findFirst(nums []int, target int) int {
    left, right := 0, len(nums)-1
    result := -1
    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] == target {
            result = mid
            right = mid - 1
        } else if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return result
}

Ruby:

def find_first(nums, target)
  left, right = 0, nums.length - 1
  result = -1
  while left <= right
    mid = left + (right - left) / 2
    if nums[mid] == target
      result = mid
      right = mid - 1
    elsif nums[mid] < target
      left = mid + 1
    else
      right = mid - 1
    end
  end
  result
end

Practice

Ready to apply these templates? Head over to the Practice Problems page to solve curated challenges.