Bisect Good Bad Automation Script in Python
This Python script implements a binary search to find the first bad version in a list, simulating an automation script for git bisect.
Python code
29 linesimport bisect
def find_first_bad(versions):
"""Given a list of version objects with .is_bad(), find first bad version."""
lo, hi = 0, len(versions)
while lo < hi:
mid = (lo + hi) // 2
if versions[mid].is_bad():
hi = mid
else:
lo = mid + 1
return lo
class Version:
def __init__(self, num, bad_start):
self.num = num
self.bad_start = bad_start
def is_bad(self):
return self.num >= self.bad_start
def __repr__(self):
return f"v{self.num}"
if __name__ == "__main__":
bad_start = 7
versions = [Version(i, bad_start) for i in range(1, 11)]
first_bad = find_first_bad(versions)
print(f"First bad version index: {first_bad} -> {versions[first_bad]}")
Output
First bad version index: 6 -> v7
How it works
The script uses a custom Version class with an is_bad() method to simulate version behavior. The binary search narrows down the first bad version by checking the middle element: if it's bad, move the high pointer down; otherwise, move the low pointer up. This guarantees O(log n) performance, making it efficient for large version histories. The output shows the index (6) and the actual version object (v7), confirming the first bad version.
Common mistakes
- Using `bisect` module incorrectly instead of custom binary search
- Off-by-one errors in the high bound, causing missing the last version
- Assuming versions start at index 1 when using the result as an index
Variations
- Use `bisect.bisect_left` with a key function for simpler code
- Implement with recursive binary search for clarity
Real-world use cases
- Automating git bisect to identify the commit that introduced a regression.
- Finding the first failing test in a sequence of test runs during CI.
- Locating the first incompatible change in a deployment pipeline.
Sponsored
More from Git + Python
- Amend Last Commit Message in Python easy
- Build a Simple Log Graph in Python easy
- Bump Semantic Version Git Tag in Python easy
- Count Unique Contributors from Git Shortlog in Python easy
- Create a Mock GitHub Release API in Python for Testing gh CLI easy
- Detect Merge Conflict Markers in a File with Python easy
Keep learning
Related tutorials and quizzes for this topic.