fork download
copy 
  1. # recursion 1
  2. def binsearch(lo, hi, list, key):
  3.     if lo > hi:
  4.        return False
  5.     p = ( lo + hi ) >> 1
  6.     if key == list[p]:
  7.        return True
  8.     if key > list[p]:
  9.        return binsearch(p+1, hi, list, key)
  10.     else:
  11.        return binsearch(lo, p - 1, list, key)
  12.  
  13. # recursion 2
  14. def _binsearch(lo, hi, list, key):
  15.     if lo <= hi:
  16.       p = ( lo + hi ) >> 1
  17.       if key == list[p]:
  18.           return True
  19.       if key > list[p]:
  20.           return binsearch(p+1, hi, list, key)
  21.       else:
  22.           return binsearch(lo, p - 1, list, key)
  23.     return False
  24.  
  25. #iteration 1
  26. def _binsearch_(lo, hi, list, key):
  27.     pos = False
  28.     while lo <= hi:
  29.         p = (lo + hi ) >> 1
  30.         if list[p] == key:
  31.             pos = True
  32.             break
  33.         elif key > list[p]:
  34.             lo = p + 1
  35.         else:
  36.             hi = p - 1
  37.     return pos
  38.  
  39. #iteration 2
  40. def _binsearch_2(lo, hi, list, key):
  41.  
  42.     pos = False
  43.     while not lo > hi and pos is False:
  44.         p = (lo + hi ) >> 1
  45.         if list[p] == key:
  46.             pos = True
  47.         elif key > list[p]:
  48.             lo = p + 1
  49.         else:
  50.             hi = p - 1
  51.     return pos
  52.  
  53.  
  54. def searchBin(list, key):
  55.     return _binsearch_2(0, len(list)-1, list, key)
  56.  
  57. # non recursion => iteration
  58. def main():
  59.     list = [-3,-1,11,22,44,55,77,88,101]
  60.     print(list)
  61.     key = -3
  62.     if searchBin(list,key) is True:
  63.        print(f'{key} exists in List')
  64.     else:
  65.        print(f'{key} not exist in List')
  66. main()
  67.  
Success #stdin #stdout 0.03s 9072KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[-3, -1, 11, 22, 44, 55, 77, 88, 101]
-3 exists in List
https://ideone.com/uIgbB1
Class7C Binary Search in Python
language:
Python 3 (python  3.9.5)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!