<jupyter_start><jupyter_text>The binary search is a simple and very useful algorithm whereby many linear algorithms canbe optimized to run in logarithmic time.   Binary search in O(log n)<jupyter_code>def binary_search(A, x):
    first = 0
    last = len(A) - 1
    found = False
    index = -1
    
    while first<=last and not found:
        midpoint = (first + last) // 2
        if A[midpoint] == x:
            found = True
            index = midpoint
        else:
            if x < A[midpoint]:
                last = midpoint - 1
            else:
                first = midpoint + 1

    return found, index
import random
A = sorted([random.randint(1, 20) for _ in range(10)])
print(A)
binary_search(A, 13)
import random
A = sorted([random.randint(1, 20) for _ in range(10)])
print(A)
binary_search(A, 13)
import random
A = sorted([random.randint(1, 20) for _ in range(10)])
print(A)
binary_search(A, 13)<jupyter_output>[4, 4, 5, 8, 8, 9, 10, 11, 13, 19]<jupyter_text>**Problem:** You are given n binary values x0, x1, . . . , xn−1, such that xi ∈ {0, 1}. This arrayrepresents holes in a roof (1 is a hole). You are also given k boards of the same size. The goalis to choose the optimal (minimal) size of the boards that allows all the holes to be coveredby boards.<jupyter_code>def boards(A, k):
    n = len(A)
    beg = 1
    end = n
    result = -1
    while (beg <= end):
        mid = (beg + end) // 2
        if (check(A, mid) <= k):
            end = mid - 1
            result = mid
        else:
            beg = mid + 1
    return result

def check(A, k):
    n = len(A)
    boards = 0
    last = -1
    for i in range(n):
        if A[i] == 1 and last < i:
            boards += 1
            last = i + k - 1
    return boards
import random
A = [random.randint(0, 1) for _ in range(20)]
print(A)
boards(A, 3)<jupyter_output>[1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1]
{'fraction_non_alphanumeric': 0.12303664921465969, 'fraction_numerical': 0.04293193717277487, 'mean_word_length': 2.185, 'pattern_counts': {'":': 0, '<': 12, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '302120', 'license': 'MIT', 'n_tokens_mistral': 741, 'n_tokens_neox': 659, 'n_words': 253, 'path': 'examples/Binary search algorithm.ipynb', 'repo_name': 'jeff00seattle/pyfortified-notebooks', 'size': '1910'}