概要二分検索アルゴリズムと関連するPython実装例

二分ルックアップBinary Searchの考え方:静的ルックアップテーブルを秩序テーブルで表す場合、ルックアップ関数は二分ルックアップで実現できる.二分探索(Binary Search)の探索プロセスは、まず、調査対象レコードが存在する区間を決定し、その後、そのレコードが見つかったり見つからなかったりするまで区間を徐々に縮小することである.1二分探索の時間的複雑度はO(log(n)),最悪の場合の時間的複雑度はO(n)である.lowが区間下界を指し、highが区間上界を指し、midが区間の中間位置を指すと仮定すると、mid=(low+high)/2;具体的な過程:1.キーワードをmidが指す要素と比較し、等しい場合はmidを返します.2.キーワードがmidが指す要素キーワードより小さい場合は、[low,mid-1]区間で二分検索を継続します.3.キーワードがmidが指す要素キーワードより大きい場合は、[mid+1,high]区間で二分検索を継続します.
Pythonによる二分検索の例:

>>> def find(self, num):
  l = len(self)
  first = 0
  end = l - 1
  mid = 0
  if l == 0:
   self.insert(0,num)
   return False
  while first < end:
   mid = (first + end)/2
   if num > self[mid]:
    first = mid + 1
   elif num < self[mid]:
    end = mid - 1
   else:
    break
  if first == end:
   if self[first] > num:
    self.insert(first, num)
    return False
   elif self[first] < num:
    self.insert(first + 1, num)
    return False
   else:
    return True
  elif first > end:
   self.insert(first, num)
   return False
  else:
   return True

>>> list_d = ['a','b','c','d','e','f','d','t']
>>> value_d = 't'
>>> aa=find(list_d,value_d)
>>> aa
True
>>> value_d='ha'
>>> aa=find(list_d,value_d)
>>> aa
False