<jupyter_start><jupyter_text>Searching and Recursion* Logarithms* Types of problems where you might find `O(log n)` solutions* Linear search refresher* Binary Search* Introduction to Recursion**Attendance code: 7349**<jupyter_code>import random

random.seed(3490)
numbers = [random.randrange(200) for _ in range(20)]

print(numbers)

# Linear search
for i in numbers:   # O(n) over the len(numbers)
    if i == 66:
        print("Found it!")

numbers.sort()  # O(n * log n)

print(numbers)

# Now that it's sorted, we can do Binary Search instead

# A process might be O(log n) if each step halves the remaining data to be processed
# IOW effectively doubles the amount of data processed each step<jupyter_output>[129, 34, 192, 148, 46, 3, 150, 53, 153, 102, 160, 159, 66, 88, 37, 175, 89, 8, 10, 185]
Found it!
[3, 8, 10, 34, 37, 46, 53, 66, 88, 89, 102, 129, 148, 150, 153, 159, 160, 175, 185, 192]<jupyter_text>What is log n?Logarithms are like the opposites of exponentsCS when we say log n, we mean log_2 n.``` n2  = xlog_2 x = n     As x gets big, n remains relatively small``````2^5 == 32elements   operationsto process     |      v        vlog_2 16    == 4log_2 32    == 5log_2 64    == 6log_2 128   == 7log_2 256   == 8log_2 65536 == 16log_2 4294967296 == 32```<jupyter_code># Binary Search

def binary_search(numbers, target):
    # Return the index we find the target at, or -1 if we don't find it

    iterations = 0

    # Start min_index at 0
    min_index = 0

    # Start max_index at len(numbers) - 1
    max_index = len(numbers) - 1

    # Loop until max_index < min_index:
    while min_index <= max_index:
        iterations += 1

        # Find the middle index by averaging min_index and max_index (min + max) // 2
        current = (min_index + max_index) // 2

        # if value at current == target: return current
        if numbers[current] == target:
            return (current, iterations)

        # if value at current < target:
        if numbers[current] < target:
            # move min to current + 1
            min_index = current + 1
        # else: # value at current > target
        else:
            # move max to current - 1
            max_index = current - 1

    # If we get here, not found, return -1
    return (-1, iterations)

"""
numbers = [3, 8, 10, 34, 37, 46, 53, 66, 88, 89, 102, 129, 148, 150, 153, 159, 160, 175, 185, 192]

for n in numbers:
    print(binary_search(numbers, n))
"""

print("Building lists...")
random.seed(3490)
numbers = [random.randrange(500000) for _ in range(10000000)]

print("Sorting...")
numbers.sort()  # O(n * log n)

print("Searching...")
for i in range(2000, 2200):
    print(binary_search(numbers,i)) # O(log n)<jupyter_output>Building lists...
Sorting...
Searching...
(39518, 16)
(39537, 19)
(39556, 18)
(39575, 19)
(39594, 17)
(39613, 19)
(39632, 18)
(39651, 19)
(39671, 14)
(39690, 19)
(39709, 18)
(39728, 19)
(39747, 17)
(39766, 19)
(39785, 18)
(39823, 16)
(39842, 19)
(39861, 18)
(39899, 17)
(39918, 19)
(39937, 18)
(39956, 19)
(39976, 15)
(39995, 19)
(40014, 18)
(40033, 19)
(40052, 17)
(40061, 20)
(40071, 19)
(40090, 18)
(40109, 19)
(40128, 16)
(40166, 18)
(40175, 20)
(40204, 17)
(40213, 20)
(40242, 18)
(40251, 20)
(40261, 19)
(40281, 13)
(40300, 19)
(40319, 18)
(40338, 19)
(40357, 17)
(40376, 19)
(40395, 18)
(40433, 16)
(40452, 19)
(40471, 18)
(40509, 17)
(40528, 19)
(40547, 18)
(40566, 19)
(40576, 20)
(40586, 15)
(40624, 18)
(40643, 19)
(40662, 17)
(40681, 19)
(40700, 18)
(40719, 19)
(40738, 16)
(40776, 18)
(40795, 19)
(40814, 17)
(40833, 19)
(40852, 18)
(40871, 19)
(40891, 14)
(40929, 18)
(40948, 19)
(40967, 17)
(40986, 19)
(41005, 18)
(41024, 19)
(41043, 16)
(41062, 19)
(41081, 18)
(41119, 17)
(41128, 20[...]<jupyter_text>Intro to RecursionFunctions calling themselves. How to spot a recursive problemSee if you find how the problem is composed of identical subproblems. Print a listRecursively!```a = [1,2,3,4,5,6,7]``````print_a_list(x):    print(x[0])    print_a_list(x[1:])   slice the rest of the list and pass it in```<jupyter_code>a = [1,2,3,4]

def print_a_list(x):
    # Base case
    if x == []:
        return

    print("inbound", x[0])
    print_a_list(x[1:])
    print("outbound", x[0])

print_a_list(a)
# Fibonacci Sequence
#
# 0 1 2 3 4 5 6 7  8  9  10 11
# 0 1 1 2 3 5 8 13 21 34 55 89 ...
#
# Compute the nth Fibonacci number
#
# fib(0): 0
# fib(1): 1
# fib(n): fib(n-1) + fib(n-2)

def fib(n):
    # Base cases
    if n == 0: return 0
    if n == 1: return 1

    return fib(n-1) + fib(n-2)
    
for i in range(37):
    print(i, fib(i))
# Bonus info: "memoization"

cache = {}

def fib(n):
    # Base cases
    if n == 0: return 0
    if n == 1: return 1

    if n not in cache:
        cache[n] = fib(n-1) + fib(n-2)

    return cache[n]
    
for i in range(1000):
    print(i, fib(i))<jupyter_output>0 0
1 1
2 1
3 2
4 3
5 5
6 8
7 13
8 21
9 34
10 55
11 89
12 144
13 233
14 377
15 610
16 987
17 1597
18 2584
19 4181
20 6765
21 10946
22 17711
23 28657
24 46368
25 75025
26 121393
27 196418
28 317811
29 514229
30 832040
31 1346269
32 2178309
33 3524578
34 5702887
35 9227465
36 14930352
37 24157817
38 39088169
39 63245986
40 102334155
41 165580141
42 267914296
43 433494437
44 701408733
45 1134903170
46 1836311903
47 2971215073
48 4807526976
49 7778742049
50 12586269025
51 20365011074
52 32951280099
53 53316291173
54 86267571272
55 139583862445
56 225851433717
57 365435296162
58 591286729879
59 956722026041
60 1548008755920
61 2504730781961
62 4052739537881
63 6557470319842
64 10610209857723
65 17167680177565
66 27777890035288
67 44945570212853
68 72723460248141
69 117669030460994
70 190392490709135
71 308061521170129
72 498454011879264
73 806515533049393
74 1304969544928657
75 2111485077978050
76 3416454622906707
77 5527939700884757
78 8944394323791464
79 14472334024676221
80 2341672834846[...]
{'fraction_non_alphanumeric': 0.12744090441932168, 'fraction_numerical': 0.2946214457005824, 'mean_word_length': 3.4167927382753405, 'pattern_counts': {'":': 0, '<': 14, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 1, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '181753', 'license': 'MIT', 'n_tokens_mistral': 3634, 'n_tokens_neox': 2378, 'n_words': 812, 'path': 'CS42_DS_&_A_1_M4_Searching_and_Recursion.ipynb', 'repo_name': 'juancaruizc/CS42-DS-A-1-M4-Searching-and-Recursion', 'size': '5838'}