How to find an impostor binary search implementation in Python! :-)

03810

Recently I have been working on writing STL algorithms of C++ in Python (here). I came across a typical problem, which was how to test the implementation of binary search algorithm? Let us write some tests first.
You can write tests using any Python testing framework like pytest , unittest etc, here I am using unittest which is part of Python Standard Library. 

<span>import</span> <span>random</span>
<span>import</span> <span>unittest</span>
<span>from</span> <span>binary_search</span> <span>import</span> <span>binary_search</span>
<span>class</span> <span>BinarySearchTestCase</span><span>(</span><span>unittest</span><span>.</span><span>TestCase</span><span>):</span>
    <span>def</span> <span>test_empty</span><span>(</span><span>self</span><span>):</span>
        <span>arr</span> <span>=</span> <span>[]</span>
        <span>self</span><span>.</span><span>assertFalse</span><span>(</span><span>binary_search</span><span>(</span><span>arr</span><span>,</span> <span>5</span><span>))</span>
    <span>def</span> <span>test_true</span><span>(</span><span>self</span><span>):</span>
        <span>arr</span> <span>=</span> <span>[</span><span>1</span><span>,</span><span>2</span><span>,</span><span>3</span><span>,</span><span>4</span><span>,</span><span>5</span><span>]</span>
        <span>self</span><span>.</span><span>assertTrue</span><span>(</span><span>binary_search</span><span>(</span><span>arr</span><span>,</span> <span>4</span><span>))</span>
    <span>def</span> <span>test_false</span><span>(</span><span>self</span><span>):</span>
        <span>arr</span> <span>=</span> <span>[</span><span>1</span><span>,</span><span>2</span><span>,</span><span>3</span><span>,</span><span>4</span><span>,</span><span>5</span><span>]</span>
        <span>self</span><span>.</span><span>assertFalse</span><span>(</span><span>binary_search</span><span>(</span><span>arr</span><span>,</span> <span>99</span><span>))</span>
    <span>def</span> <span>test_on_random_list_false</span><span>(</span><span>self</span><span>):</span>
        <span>arr</span> <span>=</span> <span>[</span><span>random</span><span>.</span><span>randint</span><span>(</span><span>-</span><span>500</span><span>,</span> <span>500</span><span>)</span> <span>for</span> <span>_</span> <span>in</span> <span>range</span><span>(</span><span>500</span><span>)]</span>
        <span>arr</span><span>.</span><span>sort</span><span>()</span>
        <span>self</span><span>.</span><span>assertFalse</span><span>(</span><span>binary_search</span><span>(</span><span>arr</span><span>,</span> <span>999</span><span>))</span>
<span>if</span> <span>__name__</span> <span>==</span> <span>'__main__'</span><span>:</span>
    <span>unittest</span><span>.</span><span>main</span><span>()</span>
<span>import</span> <span>random</span>
<span>import</span> <span>unittest</span>

<span>from</span> <span>binary_search</span> <span>import</span> <span>binary_search</span>

<span>class</span> <span>BinarySearchTestCase</span><span>(</span><span>unittest</span><span>.</span><span>TestCase</span><span>):</span>

    <span>def</span> <span>test_empty</span><span>(</span><span>self</span><span>):</span>
        <span>arr</span> <span>=</span> <span>[]</span>
        <span>self</span><span>.</span><span>assertFalse</span><span>(</span><span>binary_search</span><span>(</span><span>arr</span><span>,</span> <span>5</span><span>))</span>

    <span>def</span> <span>test_true</span><span>(</span><span>self</span><span>):</span>
        <span>arr</span> <span>=</span> <span>[</span><span>1</span><span>,</span><span>2</span><span>,</span><span>3</span><span>,</span><span>4</span><span>,</span><span>5</span><span>]</span>
        <span>self</span><span>.</span><span>assertTrue</span><span>(</span><span>binary_search</span><span>(</span><span>arr</span><span>,</span> <span>4</span><span>))</span>

    <span>def</span> <span>test_false</span><span>(</span><span>self</span><span>):</span>
        <span>arr</span> <span>=</span> <span>[</span><span>1</span><span>,</span><span>2</span><span>,</span><span>3</span><span>,</span><span>4</span><span>,</span><span>5</span><span>]</span>
        <span>self</span><span>.</span><span>assertFalse</span><span>(</span><span>binary_search</span><span>(</span><span>arr</span><span>,</span> <span>99</span><span>))</span>

    <span>def</span> <span>test_on_random_list_false</span><span>(</span><span>self</span><span>):</span>
        <span>arr</span> <span>=</span> <span>[</span><span>random</span><span>.</span><span>randint</span><span>(</span><span>-</span><span>500</span><span>,</span> <span>500</span><span>)</span> <span>for</span> <span>_</span> <span>in</span> <span>range</span><span>(</span><span>500</span><span>)]</span>
        <span>arr</span><span>.</span><span>sort</span><span>()</span>
        <span>self</span><span>.</span><span>assertFalse</span><span>(</span><span>binary_search</span><span>(</span><span>arr</span><span>,</span> <span>999</span><span>))</span>

<span>if</span> <span>__name__</span> <span>==</span> <span>'__main__'</span><span>:</span>
    <span>unittest</span><span>.</span><span>main</span><span>()</span>
import random
import unittest

from binary_search import binary_search

class BinarySearchTestCase(unittest.TestCase):

    def test_empty(self):
        arr = []
        self.assertFalse(binary_search(arr, 5))

    def test_true(self):
        arr = [1,2,3,4,5]
        self.assertTrue(binary_search(arr, 4))

    def test_false(self):
        arr = [1,2,3,4,5]
        self.assertFalse(binary_search(arr, 99))

    def test_on_random_list_false(self):
        arr = [random.randint(-500, 500) for _ in range(500)]
        arr.sort()
        self.assertFalse(binary_search(arr, 999))

if __name__ == '__main__':
    unittest.main()

Enter fullscreen mode Exit fullscreen mode

The testcases are divided as follows:

  • Searching for any element in an empty list should result False.
  • Searching for an element present in the list should result True.
  • Searching for an element not present in the list should result False.

The above testcases seem reasonable. To be more robust about writing the testcases we should use hypothesis library which is the Python port of QuickCheck library in Haskell. You can simply install it using pip install hypothesis.
The tests using hypothesis are as below: 

<span>import</span> <span>random</span>
<span>import</span> <span>unittest</span>
<span>from</span> <span>hypothesis</span> <span>import</span> <span>given</span>
<span>import</span> <span>hypothesis.strategies</span> <span>as</span> <span>st</span>
<span>from</span> <span>binary_search</span> <span>import</span> <span>binary_search</span>
<span>class</span> <span>BinarySearchTestCase</span><span>(</span><span>unittest</span><span>.</span><span>TestCase</span><span>):</span>
    <span>@</span><span>given</span><span>(</span><span>st</span><span>.</span><span>integers</span><span>())</span>
    <span>def</span> <span>test_empty</span><span>(</span><span>self</span><span>,</span> <span>target</span><span>):</span>
        <span>arr</span> <span>=</span> <span>[]</span>
        <span>arr</span><span>.</span><span>sort</span><span>()</span>
        <span>self</span><span>.</span><span>assertFalse</span><span>(</span><span>binary_search</span><span>(</span><span>arr</span><span>,</span> <span>target</span><span>))</span>
    <span>@</span><span>given</span><span>(</span><span>st</span><span>.</span><span>lists</span><span>(</span><span>st</span><span>.</span><span>integers</span><span>(),</span> <span>min_size</span><span>=</span><span>1</span><span>))</span>
    <span>def</span> <span>test_binary_search_true</span><span>(</span><span>self</span><span>,</span> <span>arr</span><span>):</span>
        <span>arr</span><span>.</span><span>sort</span><span>()</span>
        <span>target</span> <span>=</span> <span>random</span><span>.</span><span>choice</span><span>(</span><span>arr</span><span>)</span>
        <span>self</span><span>.</span><span>assertTrue</span><span>(</span><span>binary_search</span><span>(</span><span>arr</span><span>,</span> <span>target</span><span>))</span>
    <span>@</span><span>given</span><span>(</span><span>st</span><span>.</span><span>lists</span><span>(</span><span>st</span><span>.</span><span>integers</span><span>(),</span> <span>min_size</span><span>=</span><span>1</span><span>))</span>
    <span>def</span> <span>test_binary_search_false</span><span>(</span><span>self</span><span>,</span> <span>arr</span><span>):</span>
        <span>arr</span><span>.</span><span>sort</span><span>()</span>
        <span>target</span> <span>=</span> <span>arr</span><span>[</span><span>-</span><span>1</span><span>]</span> <span>+</span> <span>1</span>
        <span>self</span><span>.</span><span>assertFalse</span><span>(</span><span>binary_search</span><span>(</span><span>arr</span><span>,</span> <span>target</span><span>))</span>
<span>if</span> <span>__name__</span> <span>==</span> <span>'__main__'</span><span>:</span>
    <span>unittest</span><span>.</span><span>main</span><span>()</span>
<span>import</span> <span>random</span>
<span>import</span> <span>unittest</span>

<span>from</span> <span>hypothesis</span> <span>import</span> <span>given</span>
<span>import</span> <span>hypothesis.strategies</span> <span>as</span> <span>st</span>

<span>from</span> <span>binary_search</span> <span>import</span> <span>binary_search</span>


<span>class</span> <span>BinarySearchTestCase</span><span>(</span><span>unittest</span><span>.</span><span>TestCase</span><span>):</span>

    <span>@</span><span>given</span><span>(</span><span>st</span><span>.</span><span>integers</span><span>())</span>
    <span>def</span> <span>test_empty</span><span>(</span><span>self</span><span>,</span> <span>target</span><span>):</span>
        <span>arr</span> <span>=</span> <span>[]</span>
        <span>arr</span><span>.</span><span>sort</span><span>()</span>
        <span>self</span><span>.</span><span>assertFalse</span><span>(</span><span>binary_search</span><span>(</span><span>arr</span><span>,</span> <span>target</span><span>))</span>

    <span>@</span><span>given</span><span>(</span><span>st</span><span>.</span><span>lists</span><span>(</span><span>st</span><span>.</span><span>integers</span><span>(),</span> <span>min_size</span><span>=</span><span>1</span><span>))</span>
    <span>def</span> <span>test_binary_search_true</span><span>(</span><span>self</span><span>,</span> <span>arr</span><span>):</span>
        <span>arr</span><span>.</span><span>sort</span><span>()</span>
        <span>target</span> <span>=</span> <span>random</span><span>.</span><span>choice</span><span>(</span><span>arr</span><span>)</span>
        <span>self</span><span>.</span><span>assertTrue</span><span>(</span><span>binary_search</span><span>(</span><span>arr</span><span>,</span> <span>target</span><span>))</span>

    <span>@</span><span>given</span><span>(</span><span>st</span><span>.</span><span>lists</span><span>(</span><span>st</span><span>.</span><span>integers</span><span>(),</span> <span>min_size</span><span>=</span><span>1</span><span>))</span>
    <span>def</span> <span>test_binary_search_false</span><span>(</span><span>self</span><span>,</span> <span>arr</span><span>):</span>
        <span>arr</span><span>.</span><span>sort</span><span>()</span>
        <span>target</span> <span>=</span> <span>arr</span><span>[</span><span>-</span><span>1</span><span>]</span> <span>+</span> <span>1</span>
        <span>self</span><span>.</span><span>assertFalse</span><span>(</span><span>binary_search</span><span>(</span><span>arr</span><span>,</span> <span>target</span><span>))</span>

<span>if</span> <span>__name__</span> <span>==</span> <span>'__main__'</span><span>:</span>
    <span>unittest</span><span>.</span><span>main</span><span>()</span>
import random
import unittest

from hypothesis import given
import hypothesis.strategies as st

from binary_search import binary_search


class BinarySearchTestCase(unittest.TestCase):

    @given(st.integers())
    def test_empty(self, target):
        arr = []
        arr.sort()
        self.assertFalse(binary_search(arr, target))

    @given(st.lists(st.integers(), min_size=1))
    def test_binary_search_true(self, arr):
        arr.sort()
        target = random.choice(arr)
        self.assertTrue(binary_search(arr, target))

    @given(st.lists(st.integers(), min_size=1))
    def test_binary_search_false(self, arr):
        arr.sort()
        target = arr[-1] + 1
        self.assertFalse(binary_search(arr, target))

if __name__ == '__main__':
    unittest.main()

Enter fullscreen mode Exit fullscreen mode test.py

Hypothesis automatically generates different testcases given the specification, which in this case is a list of integers.

Now the fun part is the binary search code: 

<span>def</span> <span>binary_search</span><span>(</span><span>arr</span><span>,</span> <span>target</span><span>):</span>
    <span>return</span> <span>target</span> <span>in</span> <span>arr</span>
<span>def</span> <span>binary_search</span><span>(</span><span>arr</span><span>,</span> <span>target</span><span>):</span>
    <span>return</span> <span>target</span> <span>in</span> <span>arr</span>
def binary_search(arr, target):
    return target in arr

Enter fullscreen mode Exit fullscreen mode binary_search.py

Let us run the test now. 

$ python test.py
...
----------------------------------------------------------------------
Ran 3 tests in 0.380s
OK
$ python test.py
...
----------------------------------------------------------------------
Ran 3 tests in 0.380s

OK
$ python test.py
...
----------------------------------------------------------------------
Ran 3 tests in 0.380s

OK

Enter fullscreen mode Exit fullscreen mode

The above code is no where near the binary search implementation, but passes all the tests! The linear search algorithm passes the binary search testcases! What?? Now how can we rule out this impostor code?

The problem with these tests are that it doesn’t use any of the property of binary search algorithm, it just checks the property of a searching algorithm.

We know one property of binary search that at maximum log2(n) + 1 items will be seen, as it discards half the search space at every iteration.
Here n is the total number of elements in the array.

So we write a class which behaves like a list, by implementing __iter__ and __getitem__ special methods. 

<span>class</span> <span>Node</span><span>:</span>
    <span>def</span> <span>__init__</span><span>(</span><span>self</span><span>,</span> <span>arr</span><span>):</span>
        <span>self</span><span>.</span><span>arr</span> <span>=</span> <span>arr</span>
        <span>self</span><span>.</span><span>count</span> <span>=</span> <span>0</span>
    <span>def</span> <span>__iter__</span><span>(</span><span>self</span><span>):</span>
        <span>for</span> <span>x</span> <span>in</span> <span>self</span><span>.</span><span>arr</span><span>:</span>
            <span>self</span><span>.</span><span>count</span> <span>+=</span> <span>1</span>
            <span>yield</span> <span>x</span>
    <span>def</span> <span>__getitem__</span><span>(</span><span>self</span><span>,</span> <span>key</span><span>):</span>
        <span>self</span><span>.</span><span>count</span> <span>+=</span> <span>1</span>
        <span>return</span> <span>self</span><span>.</span><span>arr</span><span>[</span><span>key</span><span>]</span>
    <span>def</span> <span>__len__</span><span>(</span><span>self</span><span>):</span>
        <span>return</span> <span>len</span><span>(</span><span>self</span><span>.</span><span>arr</span><span>)</span>
<span>class</span> <span>Node</span><span>:</span>
    <span>def</span> <span>__init__</span><span>(</span><span>self</span><span>,</span> <span>arr</span><span>):</span>
        <span>self</span><span>.</span><span>arr</span> <span>=</span> <span>arr</span>
        <span>self</span><span>.</span><span>count</span> <span>=</span> <span>0</span>

    <span>def</span> <span>__iter__</span><span>(</span><span>self</span><span>):</span>
        <span>for</span> <span>x</span> <span>in</span> <span>self</span><span>.</span><span>arr</span><span>:</span>
            <span>self</span><span>.</span><span>count</span> <span>+=</span> <span>1</span>
            <span>yield</span> <span>x</span>

    <span>def</span> <span>__getitem__</span><span>(</span><span>self</span><span>,</span> <span>key</span><span>):</span>
        <span>self</span><span>.</span><span>count</span> <span>+=</span> <span>1</span>
        <span>return</span> <span>self</span><span>.</span><span>arr</span><span>[</span><span>key</span><span>]</span>

    <span>def</span> <span>__len__</span><span>(</span><span>self</span><span>):</span>
        <span>return</span> <span>len</span><span>(</span><span>self</span><span>.</span><span>arr</span><span>)</span>
class Node:
    def __init__(self, arr):
        self.arr = arr
        self.count = 0

    def __iter__(self):
        for x in self.arr:
            self.count += 1
            yield x

    def __getitem__(self, key):
        self.count += 1
        return self.arr[key]

    def __len__(self):
        return len(self.arr)

Enter fullscreen mode Exit fullscreen mode

We now have a Node class which is similar to list class but additionally has a count variable, which increments every time an element is accessed. This will help to keep track of how many elements the binary search code checks.

In Python, there is a saying, if something walks like a duck, quacks like a duck, it is a duck.

We add this extra testcase using the above Node class. 

<span>import</span> <span>math</span>
<span>@</span><span>given</span><span>(</span><span>st</span><span>.</span><span>lists</span><span>(</span><span>st</span><span>.</span><span>integers</span><span>(),</span> <span>min_size</span><span>=</span><span>1</span><span>))</span>
<span>def</span> <span>test_binary_search_with_node</span><span>(</span><span>self</span><span>,</span> <span>arr</span><span>):</span>
    <span>arr</span><span>.</span><span>sort</span><span>()</span>
    <span>target</span> <span>=</span> <span>arr</span><span>[</span><span>-</span><span>1</span><span>]</span>
    <span>max_count</span> <span>=</span> <span>int</span><span>(</span><span>math</span><span>.</span><span>log2</span><span>(</span><span>len</span><span>(</span><span>arr</span><span>)))</span> <span>+</span> <span>1</span> 
    <span>arr</span> <span>=</span> <span>Node</span><span>(</span><span>arr</span><span>)</span>
    <span>ans</span> <span>=</span> <span>binary_search</span><span>(</span><span>arr</span><span>,</span> <span>target</span><span>)</span>
    <span>self</span><span>.</span><span>assertTrue</span><span>(</span><span>ans</span><span>)</span>
    <span>self</span><span>.</span><span>assertTrue</span><span>(</span><span>arr</span><span>.</span><span>count</span> <span><=</span> <span>max_count</span><span>)</span>
<span>import</span> <span>math</span>

<span>@</span><span>given</span><span>(</span><span>st</span><span>.</span><span>lists</span><span>(</span><span>st</span><span>.</span><span>integers</span><span>(),</span> <span>min_size</span><span>=</span><span>1</span><span>))</span>
<span>def</span> <span>test_binary_search_with_node</span><span>(</span><span>self</span><span>,</span> <span>arr</span><span>):</span>
    <span>arr</span><span>.</span><span>sort</span><span>()</span>
    <span>target</span> <span>=</span> <span>arr</span><span>[</span><span>-</span><span>1</span><span>]</span>
    <span>max_count</span> <span>=</span> <span>int</span><span>(</span><span>math</span><span>.</span><span>log2</span><span>(</span><span>len</span><span>(</span><span>arr</span><span>)))</span> <span>+</span> <span>1</span> 
    <span>arr</span> <span>=</span> <span>Node</span><span>(</span><span>arr</span><span>)</span>
    <span>ans</span> <span>=</span> <span>binary_search</span><span>(</span><span>arr</span><span>,</span> <span>target</span><span>)</span>
    <span>self</span><span>.</span><span>assertTrue</span><span>(</span><span>ans</span><span>)</span>
    <span>self</span><span>.</span><span>assertTrue</span><span>(</span><span>arr</span><span>.</span><span>count</span> <span><=</span> <span>max_count</span><span>)</span>
import math

@given(st.lists(st.integers(), min_size=1))
def test_binary_search_with_node(self, arr):
    arr.sort()
    target = arr[-1]
    max_count = int(math.log2(len(arr))) + 1 
    arr = Node(arr)
    ans = binary_search(arr, target)
    self.assertTrue(ans)
    self.assertTrue(arr.count <= max_count)

Enter fullscreen mode Exit fullscreen mode

Let us run the tests again now: 

$ python test.py
..Falsifying example: test_binary_search_with_node(
    self=<__main__.BinarySearchTestCase testMethod=test_binary_search_with_node>,
    arr=[0, 0, 1],
)
F.
======================================================================
FAIL: test_binary_search_with_node (__main__.BinarySearchTestCase)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "code.py", line 48, in test_binary_search_with_node
    def test_binary_search_with_node(self, arr):
  File "/home/tmp/venv/lib/python3.6/site-packages/hypothesis/core.py", line 1162, in wrapped_test
    raise the_error_hypothesis_found
  File "code.py", line 54, in test_binary_search_with_node
    self.assertTrue(arr.count <= math.log2(len(arr)) + 1)
AssertionError: False is not true
---------------------------------------------------------------------------
Ran 4 tests in 0.435s
FAILED (failures=1)
$ python test.py
..Falsifying example: test_binary_search_with_node(
    self=<__main__.BinarySearchTestCase testMethod=test_binary_search_with_node>,
    arr=[0, 0, 1],
)
F.
======================================================================
FAIL: test_binary_search_with_node (__main__.BinarySearchTestCase)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "code.py", line 48, in test_binary_search_with_node
    def test_binary_search_with_node(self, arr):
  File "/home/tmp/venv/lib/python3.6/site-packages/hypothesis/core.py", line 1162, in wrapped_test
    raise the_error_hypothesis_found
  File "code.py", line 54, in test_binary_search_with_node
    self.assertTrue(arr.count <= math.log2(len(arr)) + 1)
AssertionError: False is not true

---------------------------------------------------------------------------
Ran 4 tests in 0.435s

FAILED (failures=1)
$ python test.py
..Falsifying example: test_binary_search_with_node(
    self=<__main__.BinarySearchTestCase testMethod=test_binary_search_with_node>,
    arr=[0, 0, 1],
)
F.
======================================================================
FAIL: test_binary_search_with_node (__main__.BinarySearchTestCase)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "code.py", line 48, in test_binary_search_with_node
    def test_binary_search_with_node(self, arr):
  File "/home/tmp/venv/lib/python3.6/site-packages/hypothesis/core.py", line 1162, in wrapped_test
    raise the_error_hypothesis_found
  File "code.py", line 54, in test_binary_search_with_node
    self.assertTrue(arr.count <= math.log2(len(arr)) + 1)
AssertionError: False is not true

---------------------------------------------------------------------------
Ran 4 tests in 0.435s

FAILED (failures=1)

Enter fullscreen mode Exit fullscreen mode

This code fails because each and every element will be checked once, which is not true for binary search. It discards half the search space at every iteration. Hypothesis also provides the minimum testcase which failed the test, which in this case is an array of size 3.
Impostor code found!

Complete test code 

<span>import</span> <span>random</span>
<span>import</span> <span>math</span>
<span>import</span> <span>unittest</span>
<span>from</span> <span>hypothesis</span> <span>import</span> <span>given</span>
<span>import</span> <span>hypothesis.strategies</span> <span>as</span> <span>st</span>
<span>from</span> <span>binary_search</span> <span>import</span> <span>binary_search</span>
<span>class</span> <span>Node</span><span>:</span>
    <span>def</span> <span>__init__</span><span>(</span><span>self</span><span>,</span> <span>arr</span><span>):</span>
        <span>self</span><span>.</span><span>arr</span> <span>=</span> <span>arr</span>
        <span>self</span><span>.</span><span>count</span> <span>=</span> <span>0</span>
    <span>def</span> <span>__iter__</span><span>(</span><span>self</span><span>):</span>
        <span>for</span> <span>x</span> <span>in</span> <span>self</span><span>.</span><span>arr</span><span>:</span>
            <span>self</span><span>.</span><span>count</span> <span>+=</span> <span>1</span>
            <span>yield</span> <span>x</span>
    <span>def</span> <span>__getitem__</span><span>(</span><span>self</span><span>,</span> <span>key</span><span>):</span>
        <span>self</span><span>.</span><span>count</span> <span>+=</span> <span>1</span>
        <span>return</span> <span>self</span><span>.</span><span>arr</span><span>[</span><span>key</span><span>]</span>
    <span>def</span> <span>__len__</span><span>(</span><span>self</span><span>):</span>
        <span>return</span> <span>len</span><span>(</span><span>self</span><span>.</span><span>arr</span><span>)</span>
<span>class</span> <span>BinarySearchTestCase</span><span>(</span><span>unittest</span><span>.</span><span>TestCase</span><span>):</span>
    <span>@</span><span>given</span><span>(</span><span>st</span><span>.</span><span>integers</span><span>())</span>
    <span>def</span> <span>test_empty</span><span>(</span><span>self</span><span>,</span> <span>target</span><span>):</span>
        <span>arr</span> <span>=</span> <span>[]</span>
        <span>arr</span><span>.</span><span>sort</span><span>()</span>
        <span>self</span><span>.</span><span>assertFalse</span><span>(</span><span>binary_search</span><span>(</span><span>arr</span><span>,</span> <span>target</span><span>))</span>
    <span>@</span><span>given</span><span>(</span><span>st</span><span>.</span><span>lists</span><span>(</span><span>st</span><span>.</span><span>integers</span><span>(),</span> <span>min_size</span><span>=</span><span>1</span><span>))</span>
    <span>def</span> <span>test_binary_search_true</span><span>(</span><span>self</span><span>,</span> <span>arr</span><span>):</span>
        <span>arr</span><span>.</span><span>sort</span><span>()</span>
        <span>target</span> <span>=</span> <span>random</span><span>.</span><span>choice</span><span>(</span><span>arr</span><span>)</span>
        <span>self</span><span>.</span><span>assertTrue</span><span>(</span><span>binary_search</span><span>(</span><span>arr</span><span>,</span> <span>target</span><span>))</span>
    <span>@</span><span>given</span><span>(</span><span>st</span><span>.</span><span>lists</span><span>(</span><span>st</span><span>.</span><span>integers</span><span>(),</span> <span>min_size</span><span>=</span><span>1</span><span>))</span>
    <span>def</span> <span>test_binary_search_false</span><span>(</span><span>self</span><span>,</span> <span>arr</span><span>):</span>
        <span>arr</span><span>.</span><span>sort</span><span>()</span>
        <span>target</span> <span>=</span> <span>arr</span><span>[</span><span>-</span><span>1</span><span>]</span> <span>+</span> <span>1</span>
        <span>self</span><span>.</span><span>assertFalse</span><span>(</span><span>binary_search</span><span>(</span><span>arr</span><span>,</span> <span>target</span><span>))</span>
    <span>@</span><span>given</span><span>(</span><span>st</span><span>.</span><span>lists</span><span>(</span><span>st</span><span>.</span><span>integers</span><span>(),</span> <span>min_size</span><span>=</span><span>1</span><span>))</span>
    <span>def</span> <span>test_binary_search_with_node</span><span>(</span><span>self</span><span>,</span> <span>arr</span><span>):</span>
        <span>arr</span><span>.</span><span>sort</span><span>()</span>
        <span>target</span> <span>=</span> <span>arr</span><span>[</span><span>-</span><span>1</span><span>]</span>
        <span>arr</span> <span>=</span> <span>Node</span><span>(</span><span>arr</span><span>)</span>
        <span>max_count</span> <span>=</span> <span>int</span><span>(</span><span>math</span><span>.</span><span>log2</span><span>(</span><span>len</span><span>(</span><span>arr</span><span>)))</span> <span>+</span> <span>1</span>
        <span>ans</span> <span>=</span> <span>binary_search</span><span>(</span><span>arr</span><span>,</span> <span>target</span><span>)</span>
        <span>self</span><span>.</span><span>assertTrue</span><span>(</span><span>ans</span><span>)</span>
        <span>self</span><span>.</span><span>assertTrue</span><span>(</span><span>arr</span><span>.</span><span>count</span> <span><=</span> <span>max_count</span><span>)</span>
<span>if</span> <span>__name__</span> <span>==</span> <span>'__main__'</span><span>:</span>
    <span>unittest</span><span>.</span><span>main</span><span>()</span>
<span>import</span> <span>random</span>
<span>import</span> <span>math</span>
<span>import</span> <span>unittest</span>

<span>from</span> <span>hypothesis</span> <span>import</span> <span>given</span>
<span>import</span> <span>hypothesis.strategies</span> <span>as</span> <span>st</span>

<span>from</span> <span>binary_search</span> <span>import</span> <span>binary_search</span>

<span>class</span> <span>Node</span><span>:</span>
    <span>def</span> <span>__init__</span><span>(</span><span>self</span><span>,</span> <span>arr</span><span>):</span>
        <span>self</span><span>.</span><span>arr</span> <span>=</span> <span>arr</span>
        <span>self</span><span>.</span><span>count</span> <span>=</span> <span>0</span>

    <span>def</span> <span>__iter__</span><span>(</span><span>self</span><span>):</span>
        <span>for</span> <span>x</span> <span>in</span> <span>self</span><span>.</span><span>arr</span><span>:</span>
            <span>self</span><span>.</span><span>count</span> <span>+=</span> <span>1</span>
            <span>yield</span> <span>x</span>

    <span>def</span> <span>__getitem__</span><span>(</span><span>self</span><span>,</span> <span>key</span><span>):</span>
        <span>self</span><span>.</span><span>count</span> <span>+=</span> <span>1</span>
        <span>return</span> <span>self</span><span>.</span><span>arr</span><span>[</span><span>key</span><span>]</span>

    <span>def</span> <span>__len__</span><span>(</span><span>self</span><span>):</span>
        <span>return</span> <span>len</span><span>(</span><span>self</span><span>.</span><span>arr</span><span>)</span>

<span>class</span> <span>BinarySearchTestCase</span><span>(</span><span>unittest</span><span>.</span><span>TestCase</span><span>):</span>

    <span>@</span><span>given</span><span>(</span><span>st</span><span>.</span><span>integers</span><span>())</span>
    <span>def</span> <span>test_empty</span><span>(</span><span>self</span><span>,</span> <span>target</span><span>):</span>
        <span>arr</span> <span>=</span> <span>[]</span>
        <span>arr</span><span>.</span><span>sort</span><span>()</span>
        <span>self</span><span>.</span><span>assertFalse</span><span>(</span><span>binary_search</span><span>(</span><span>arr</span><span>,</span> <span>target</span><span>))</span>

    <span>@</span><span>given</span><span>(</span><span>st</span><span>.</span><span>lists</span><span>(</span><span>st</span><span>.</span><span>integers</span><span>(),</span> <span>min_size</span><span>=</span><span>1</span><span>))</span>
    <span>def</span> <span>test_binary_search_true</span><span>(</span><span>self</span><span>,</span> <span>arr</span><span>):</span>
        <span>arr</span><span>.</span><span>sort</span><span>()</span>
        <span>target</span> <span>=</span> <span>random</span><span>.</span><span>choice</span><span>(</span><span>arr</span><span>)</span>
        <span>self</span><span>.</span><span>assertTrue</span><span>(</span><span>binary_search</span><span>(</span><span>arr</span><span>,</span> <span>target</span><span>))</span>

    <span>@</span><span>given</span><span>(</span><span>st</span><span>.</span><span>lists</span><span>(</span><span>st</span><span>.</span><span>integers</span><span>(),</span> <span>min_size</span><span>=</span><span>1</span><span>))</span>
    <span>def</span> <span>test_binary_search_false</span><span>(</span><span>self</span><span>,</span> <span>arr</span><span>):</span>
        <span>arr</span><span>.</span><span>sort</span><span>()</span>
        <span>target</span> <span>=</span> <span>arr</span><span>[</span><span>-</span><span>1</span><span>]</span> <span>+</span> <span>1</span>
        <span>self</span><span>.</span><span>assertFalse</span><span>(</span><span>binary_search</span><span>(</span><span>arr</span><span>,</span> <span>target</span><span>))</span>

    <span>@</span><span>given</span><span>(</span><span>st</span><span>.</span><span>lists</span><span>(</span><span>st</span><span>.</span><span>integers</span><span>(),</span> <span>min_size</span><span>=</span><span>1</span><span>))</span>
    <span>def</span> <span>test_binary_search_with_node</span><span>(</span><span>self</span><span>,</span> <span>arr</span><span>):</span>
        <span>arr</span><span>.</span><span>sort</span><span>()</span>
        <span>target</span> <span>=</span> <span>arr</span><span>[</span><span>-</span><span>1</span><span>]</span>
        <span>arr</span> <span>=</span> <span>Node</span><span>(</span><span>arr</span><span>)</span>
        <span>max_count</span> <span>=</span> <span>int</span><span>(</span><span>math</span><span>.</span><span>log2</span><span>(</span><span>len</span><span>(</span><span>arr</span><span>)))</span> <span>+</span> <span>1</span>
        <span>ans</span> <span>=</span> <span>binary_search</span><span>(</span><span>arr</span><span>,</span> <span>target</span><span>)</span>
        <span>self</span><span>.</span><span>assertTrue</span><span>(</span><span>ans</span><span>)</span>
        <span>self</span><span>.</span><span>assertTrue</span><span>(</span><span>arr</span><span>.</span><span>count</span> <span><=</span> <span>max_count</span><span>)</span>

<span>if</span> <span>__name__</span> <span>==</span> <span>'__main__'</span><span>:</span>
    <span>unittest</span><span>.</span><span>main</span><span>()</span>
import random
import math
import unittest

from hypothesis import given
import hypothesis.strategies as st

from binary_search import binary_search

class Node:
    def __init__(self, arr):
        self.arr = arr
        self.count = 0

    def __iter__(self):
        for x in self.arr:
            self.count += 1
            yield x

    def __getitem__(self, key):
        self.count += 1
        return self.arr[key]

    def __len__(self):
        return len(self.arr)

class BinarySearchTestCase(unittest.TestCase):

    @given(st.integers())
    def test_empty(self, target):
        arr = []
        arr.sort()
        self.assertFalse(binary_search(arr, target))

    @given(st.lists(st.integers(), min_size=1))
    def test_binary_search_true(self, arr):
        arr.sort()
        target = random.choice(arr)
        self.assertTrue(binary_search(arr, target))

    @given(st.lists(st.integers(), min_size=1))
    def test_binary_search_false(self, arr):
        arr.sort()
        target = arr[-1] + 1
        self.assertFalse(binary_search(arr, target))

    @given(st.lists(st.integers(), min_size=1))
    def test_binary_search_with_node(self, arr):
        arr.sort()
        target = arr[-1]
        arr = Node(arr)
        max_count = int(math.log2(len(arr))) + 1
        ans = binary_search(arr, target)
        self.assertTrue(ans)
        self.assertTrue(arr.count <= max_count)

if __name__ == '__main__':
    unittest.main()

Enter fullscreen mode Exit fullscreen mode

test.py

Where to go from here?

  • Check out this awesome talk by John Huges on Testing the hard stuff and staying sane, where he talks about how he used QuickCheck for finding and fixing bugs for different companies.
  • Check out this talk on hypothesis, the port of QuickCheck in Python by ZacHatfield-Dodds.
  • Read more on unittest framework here.

Happy learning!

原文链接：How to find an impostor binary search implementation in Python! 🙂

展开阅读全文
© 版权声明
文章版权声明 1、本网站名称：拾光赋
2、本站永久网址：https://www.blogs.ink
3、本网站的文章部分内容可能来源于网络，仅供大家学习与参考，如有侵权，请联系站长QQ：805375623进行删除处理。
4、本站一切资源不代表本站立场，并不代表本站赞同其观点和对其真实性负责。
5、本站一律禁止以任何方式发布或转载任何违法的相关信息，访客发现请向站长举报
6、本站资源大多存储在云盘，如发现链接失效，请联系我们我们会第一时间更新。

THE END
Python（EN）
# python# testing# python3# fun
喜欢就支持一下吧
点赞10 分享
Like a child, always believe in hope, I believe the dream.
像孩子一样，永远相信希望，相信梦想
kity的头像-拾光赋
相关推荐
评论 抢沙发

请登录后发表评论

    暂无评论内容

kity的头像-拾光赋
今日剩余 66.9%
本周剩余 81.0%
本月剩余 44.1%
本年剩余 79.1%
最近评论
Vito的头像-拾光赋

Vito5个月前2

你就是我心中的那首忐忑，总是让我惊心动魄
Jason.Meng的头像-拾光赋钻石会员

Jason.Meng徽章-人气大使-拾光赋5个月前2

总是会在人生的不同阶段反复爱上大佬的文章~
每日一言
Like a child, always believe in hope, I believe the dream.
像孩子一样，永远相信希望，相信梦想