Bisect

Binary Search for Bug Introduction

syntax

git bisect start
git bisect bad [commit]
git bisect good <commit>

example

git bisect start
git bisect bad          # Current commit is broken
git bisect good v1.0.0  # This tag was working

# Git checks out a middle commit, you test it:
# If it's good:
git bisect good
# If it's bad:
git bisect bad
# Repeat until Git finds the first bad commit

git bisect reset  # Return to original branch

output

Bisecting: 8 revisions left to test after this (roughly 3 steps)
a1b2c3d is the first bad commit

Note Bisect uses binary search to find the exact commit that introduced a bug. For N commits, it takes at most log2(N) steps. You can automate it with: git bisect run <test-script>

DSAInterview Prep

Binary Search — Basic Template

DSA · Binary Search

syntax

lo = 0, hi = n - 1
while lo <= hi:
  mid = lo + (hi - lo) // 2
  if found: return mid
  if target > arr[mid]: lo = mid + 1
  else: hi = mid - 1
return -1 (not found)

example

// JavaScript
function search(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

# Python
def search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

output

search([1,3,5,7,9,11,13], 9) → 4

Note Time O(log n), Space O(1). Use lo <= hi for exact match search. After the loop, lo is the insertion point (where target would go). This is equivalent to Python's bisect_left when target is not found. Memorize this template cold.

GitGit

DSAInterview Prep