snipt

Ctrl+h for KB shortcuts

Python

binary search in python

#!/usr/bin/env python
# fonte: http://rebrained.com/?p=17
# busca binária em python

def binarySearch(node,value):
    """
    >>> node1=Node(1)
    >>> node4=Node(4)
    >>> node3=Node(3,node1,node4)
    >>> node7=Node(7)
    >>> node5=Node(5,node3,node7)
    >>> binarySearch(node5,4)
    5 3 4
    >>> binarySearch(node5,5)
    5
    """
    print node.value,
    if value==node.value: return
    if value<node.value:
        binarySearch(node.left,value)
    else:
        binarySearch(node.right,value)
    return None

class Node:
    def __init__(self,value,left=None,right=None):
    	self.value=value;self.left=left;self.right=right

if __name__ == "__main__":
    import doctest
    doctest.testmod()
https://snipt.net/embed/de9e777873d50e1c4a87e71d00ea8faf/
/raw/de9e777873d50e1c4a87e71d00ea8faf/
de9e777873d50e1c4a87e71d00ea8faf
python
Python
32
2019-06-20T16:22:14
True
False
False
/api/public/snipt/4697/
binary-search-in-python
<table class="highlighttable"><tr><td class="linenos"><div class="linenodiv"><pre><a href="#L-1"> 1</a> <a href="#L-2"> 2</a> <a href="#L-3"> 3</a> <a href="#L-4"> 4</a> <a href="#L-5"> 5</a> <a href="#L-6"> 6</a> <a href="#L-7"> 7</a> <a href="#L-8"> 8</a> <a href="#L-9"> 9</a> <a href="#L-10">10</a> <a href="#L-11">11</a> <a href="#L-12">12</a> <a href="#L-13">13</a> <a href="#L-14">14</a> <a href="#L-15">15</a> <a href="#L-16">16</a> <a href="#L-17">17</a> <a href="#L-18">18</a> <a href="#L-19">19</a> <a href="#L-20">20</a> <a href="#L-21">21</a> <a href="#L-22">22</a> <a href="#L-23">23</a> <a href="#L-24">24</a> <a href="#L-25">25</a> <a href="#L-26">26</a> <a href="#L-27">27</a> <a href="#L-28">28</a> <a href="#L-29">29</a> <a href="#L-30">30</a> <a href="#L-31">31</a></pre></div></td><td class="code"><div class="highlight"><pre><span></span><span id="L-1"><a name="L-1"></a><span class="ch">#!/usr/bin/env python</span> </span><span id="L-2"><a name="L-2"></a><span class="c1"># fonte: http://rebrained.com/?p=17</span> </span><span id="L-3"><a name="L-3"></a><span class="c1"># busca binária em python</span> </span><span id="L-4"><a name="L-4"></a> </span><span id="L-5"><a name="L-5"></a><span class="k">def</span> <span class="nf">binarySearch</span><span class="p">(</span><span class="n">node</span><span class="p">,</span><span class="n">value</span><span class="p">):</span> </span><span id="L-6"><a name="L-6"></a> <span class="sd">&quot;&quot;&quot;</span> </span><span id="L-7"><a name="L-7"></a><span class="sd"> &gt;&gt;&gt; node1=Node(1)</span> </span><span id="L-8"><a name="L-8"></a><span class="sd"> &gt;&gt;&gt; node4=Node(4)</span> </span><span id="L-9"><a name="L-9"></a><span class="sd"> &gt;&gt;&gt; node3=Node(3,node1,node4)</span> </span><span id="L-10"><a name="L-10"></a><span class="sd"> &gt;&gt;&gt; node7=Node(7)</span> </span><span id="L-11"><a name="L-11"></a><span class="sd"> &gt;&gt;&gt; node5=Node(5,node3,node7)</span> </span><span id="L-12"><a name="L-12"></a><span class="sd"> &gt;&gt;&gt; binarySearch(node5,4)</span> </span><span id="L-13"><a name="L-13"></a><span class="sd"> 5 3 4</span> </span><span id="L-14"><a name="L-14"></a><span class="sd"> &gt;&gt;&gt; binarySearch(node5,5)</span> </span><span id="L-15"><a name="L-15"></a><span class="sd"> 5</span> </span><span id="L-16"><a name="L-16"></a><span class="sd"> &quot;&quot;&quot;</span> </span><span id="L-17"><a name="L-17"></a> <span class="k">print</span> <span class="n">node</span><span class="o">.</span><span class="n">value</span><span class="p">,</span> </span><span id="L-18"><a name="L-18"></a> <span class="k">if</span> <span class="n">value</span><span class="o">==</span><span class="n">node</span><span class="o">.</span><span class="n">value</span><span class="p">:</span> <span class="k">return</span> </span><span id="L-19"><a name="L-19"></a> <span class="k">if</span> <span class="n">value</span><span class="o">&lt;</span><span class="n">node</span><span class="o">.</span><span class="n">value</span><span class="p">:</span> </span><span id="L-20"><a name="L-20"></a> <span class="n">binarySearch</span><span class="p">(</span><span class="n">node</span><span class="o">.</span><span class="n">left</span><span class="p">,</span><span class="n">value</span><span class="p">)</span> </span><span id="L-21"><a name="L-21"></a> <span class="k">else</span><span class="p">:</span> </span><span id="L-22"><a name="L-22"></a> <span class="n">binarySearch</span><span class="p">(</span><span class="n">node</span><span class="o">.</span><span class="n">right</span><span class="p">,</span><span class="n">value</span><span class="p">)</span> </span><span id="L-23"><a name="L-23"></a> <span class="k">return</span> <span class="bp">None</span> </span><span id="L-24"><a name="L-24"></a> </span><span id="L-25"><a name="L-25"></a><span class="k">class</span> <span class="nc">Node</span><span class="p">:</span> </span><span id="L-26"><a name="L-26"></a> <span class="k">def</span> <span class="nf">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span><span class="n">value</span><span class="p">,</span><span class="n">left</span><span class="o">=</span><span class="bp">None</span><span class="p">,</span><span class="n">right</span><span class="o">=</span><span class="bp">None</span><span class="p">):</span> </span><span id="L-27"><a name="L-27"></a> <span class="bp">self</span><span class="o">.</span><span class="n">value</span><span class="o">=</span><span class="n">value</span><span class="p">;</span><span class="bp">self</span><span class="o">.</span><span class="n">left</span><span class="o">=</span><span class="n">left</span><span class="p">;</span><span class="bp">self</span><span class="o">.</span><span class="n">right</span><span class="o">=</span><span class="n">right</span> </span><span id="L-28"><a name="L-28"></a> </span><span id="L-29"><a name="L-29"></a><span class="k">if</span> <span class="n">__name__</span> <span class="o">==</span> <span class="s2">&quot;__main__&quot;</span><span class="p">:</span> </span><span id="L-30"><a name="L-30"></a> <span class="kn">import</span> <span class="nn">doctest</span> </span><span id="L-31"><a name="L-31"></a> <span class="n">doctest</span><span class="o">.</span><span class="n">testmod</span><span class="p">()</span> </span></pre></div> </td></tr></table>
algoritmos, python