# 2.4b.py
# created on 2016-11-13
# $Id$

def f(x):
  return x ** 2 + x - 1

def fd(x):
  return 2 * x + 1

# sequential search
def lookup_a(tab):
  n = 0
  if tab[0] < 0:
    for i in range(len(tab)):
      n = n + 1
      if tab[i] >= 0:
        break
  if tab[0] > 0:
    for i in range(len(tab)):
      n = n + 1
      if tab[i] <= 0:
        break
  if tab[0] == 0:
    return [0, n]

  if abs(tab[i-1]) < abs(tab[i]):
    return [i-1, n]
  else:
    return [i, n]

# binary seaarch
def lookup_b(tab):
  n = 0
  low = 0
  high = len(tab) - 1
  while low <= high:
    n = n + 1
    mid = int((low + high) / 2)
    cmp = tab[mid]
    print('{:2d}{:4d}{}{:}'.format(n, mid, ' ',cmp))
    if cmp > 0:
      high = mid
    elif cmp < 0:
      low = mid
    else:
      return [mid, n]
    if low + 1 == high:
      if abs(tab[low]) < abs(tab[high]):
        return [low, n]
      else:
        return [high, n]

# Newton's search
def lookup_c(x_tab, f_tab, fd_tab):
  n = 0
  if f_tab[len(f_tab)-1] > 0:
    i1  = len(f_tab) - 1
    n = n + 1
    x2 = x_tab[i1] - f_tab[i1] / fd_tab[i1]
    while 1:
      x2 = round(x2, 3)
      i2 = x_tab.index(x2)
      print('{:10d}{:10d}{:10d}{:15.3f}'.format(n,i1,i2,x2))
      if i1 == i2:
        return [i, n]
      i1 = i2
      n = n + 1
      x2 = x_tab[i1] - f_tab[i1] / fd_tab[i1]
  return [i, n]

# main
x_table  = list(map(lambda x: x / 1000, range(1001))) # 0.000 to 1.000 step 0.001
f_table  = list(map(lambda x: f(x),  x_table))
fd_table = list(map(lambda x: fd(x), x_table))

# sequential search
a = lookup_a(f_table)
i = a[0]
n = a[1]
print()
print("sequential search result")
print('{:>5}{:>5}{:>15}{:>25}'.format("n", "i", "x_table[i]", "f_table[i]"))
print(50*'-')
print('{:5}{:5}{:15}{:25}'.format(n, i, x_table[i], f_table[i]))
print(50*'-')

print()
print("binary search")
print('{:2}{:4}{}'.format('n', 'i', 'f(x)'))
print(30 * '-')
a = lookup_b(f_table)
print(30 * '-')
i = a[0]
n = a[1]
print("\nbinary search result")
print('{:>5}{:>5}{:>15}{:>25}'.format("n", "i", "x_table[i]", "f_table[i]"))
print(50 * '-')
print('{:5}{:5}{:15}{:25}'.format(n, i, x_table[i], f_table[i]))
print(50 * '-')

print("\nNewton's search")
print('{:>10}{:>10}{:>10}{:>15}'.format('n', 'i1', 'i2', 'x_table[i]'))
print(45 * '-')
a = lookup_c(x_table, f_table, fd_table)
print(45 * '-')
i = a[0]
n = a[1]
print("\nNewton's search result")
print('{:>5}{:>5}{:>15}{:>25}'.format("n", "i", "x_table[i]", "f_table[i]"))
print(50 * '-')
print('{:5}{:5}{:15}{:25}'.format(n, i, x_table[i], f_table[i]))
print(50 * '-')
# end of program
#
# below is output
#
#
# sequential search result
#     n    i     x_table[i]               f_table[i]
# --------------------------------------------------
#   620  618          0.618   -7.599999999996498e-05
# --------------------------------------------------
# 
# binary search
# n i   f(x)
# ------------------------------
#  1 500 -0.25
#  2 750 0.3125
#  3 625 0.015625
#  4 562 -0.12215599999999993
#  5 593 -0.05535100000000004
#  6 609 -0.020118999999999998
#  7 617 -0.002310999999999952
#  8 621 0.006641000000000119
#  9 619 0.0021610000000000795
# 10 618 -7.599999999996498e-05
# ------------------------------
# 
# binary search result
#     n    i     x_table[i]               f_table[i]
# --------------------------------------------------
#    10  618          0.618   -7.599999999996498e-05
# --------------------------------------------------
# 
# Newton's search
#          n        i1        i2     x_table[i]
# ---------------------------------------------
#          1      1000       667          0.667
#          2       667       619          0.619
#          3       619       618          0.618
#          4       618       618          0.618
# ---------------------------------------------
# 
# Newton's search result
#     n    i     x_table[i]               f_table[i]
# --------------------------------------------------
#     4  618          0.618   -7.599999999996498e-05
# --------------------------------------------------
# eof