Chapter 2: Analyzing Algorithms

The following are the code listings for Chapter 2. [book.py]

• Listing 2-1. Calculate models based on partial data
• Listing 2-3. Binary Array Search
• Listing 2-4. Return location of target in A
• Listing 2-5. Optimization that requires just a single value comparison
• Listing 2-6. Sample function to analyze

---

Listing 2-1. Calculate models based on partial data

import numpy as np
from scipy.optimize import curve_fit

def linear_model(n, a, b):
  return a*n + b

# Sample data
xs = [100, 1000, 10000]
ys = [0.063, 0.565, 5.946]

# Coefficients are returned as first argument
[(a,b), _]   = curve_fit(linear_model, np.array(xs), np.array(ys))
print('Linear = {}*N + {}'.format(a, b))

Listing 2-3. Binary Array Search

def binary_array_search(A, target):
  lo = 0
  hi = len(A) - 1            ❶

  while lo <= hi:            ❷
    mid = (lo + hi) // 2     ❸

    if target < A[mid]:      ❹
      hi = mid-1
    elif target > A[mid]:    ❺
      lo = mid+1
    else:
      return True            ❻

  return False               ❼

❶ Set lo and hi to be inclusive within list index positions of 0 and pass:[len(A)–1].
❷ Continue as long as there is at least one value to explore.
❸ Find midpoint value, A[mid], of remaining range A[lo .. hi].
❹ If target is smaller than A[mid], continue looking to the left of mid.
❺ If target is larger than A[mid], continue looking to the right of mid.
❻ If target is found, return True.
❼ Once lo is greater than hi, there are no values remaining to search. Report that target is not in A.

Listing 2-4. Return location of target in A

def binary_array_search(A, target):
  lo = 0
  hi = len(A) - 1

  while lo <= hi:
    mid = (lo + hi) // 2

    if target < A[mid]:
      hi = mid-1
    elif target > A[mid]:
      lo = mid+1
    else:
      return mid             ❶

  return -(lo+1)             ❷

❶ Return the value of mid since that is the location of target.
❷ Alert caller that target doesn't exist by returning the negative of lo + 1.

Listing 2-5. Optimization that requires just a single value comparison

diff = target - A[mid]
if diff < 0:
  hi = mid-1
elif diff > 0:
  lo = mid+1
else:
  return mid

Listing 2-6. Sample function to analyze

def f4(N):
  ct = 1
  while N >= 2:
    ct = ct + 1
    N = N ** 0.5
  return ct