binary search tool: Fix off by one bug, add stress tests

Revert change that introduced bug when bad item is very last item in
list. Add tests that stress limits of binary search tool and try to look
for these off-by-one errors. Specifically one test checks for the bad
item being in every index of the binary search. Another tests checks for
if every single item is bad.

TEST=Add two new stress tests, run all unit tests

Change-Id: I2d5a0bda035b2c2b4994b0378aa416da19db651d
Reviewed-on: https://chrome-internal-review.googlesource.com/271916
Commit-Ready: Cassidy Burden <cburden@google.com>
Tested-by: Cassidy Burden <cburden@google.com>
Reviewed-by: Caroline Tice <cmtice@google.com>

1 files changed, 6 insertions, 0 deletions

diff --git a/binary_search_tool/binary_search_state.py b/binary_search_tool/binary_search_state.py
index 62acd759..ef276fab 100755
--- a/binary_search_tool/binary_search_state.py
+++ b/binary_search_tool/binary_search_state.py
@@ -222,6 +222,12 @@ class BinarySearchState(object):
       # Prune is set.
       prune_index = self.binary_search.current
 
+      # If found item is last item, no new items can be found
+      if prune_index == len(self.all_items) - 1:
+        self.l.LogOutput('First bad item is the last item. Breaking.')
+        self.l.LogOutput('Bad items are: %s' % self.all_items[-1])
+        break
+
       # If already seen item we have no new bad items to find, finish up
       if self.all_items[prune_index] in self.found_items:
         self.l.LogOutput(('Found item already found before: %s. '