Python随笔33：Python基础编程练习题31~32

注：本文所有代码均经过Python 3.7实际运行检验，保证其严谨性。

Python基础练习题31：最少搜查次数

设有序表的关键字序列为[1, 4, 6, 11, 19, 35, 52, 54, 57, 71, 78, 86, 92, 96]，当用二分搜查法查找86这个结点时，最少经过多少次才能查找成功？

解答：二分搜查法是常用的算法，其原理是从列表的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。重复这个过程，直到找到要查找的元素为止。

本题因为要找的是次数，所以加入count = 0作为计数变量，然后每查找一次都用count += 1来进行计数。

l = [1, 4, 6, 11, 19, 35, 52, 54, 57, 71, 78, 86, 92, 96]
x = 86
def binary_search(l, x):
    count = 0
    low = 0
    high = len(l) - 1
    while low <= high:
        mid = (low + high) // 2
        count += 1
        guess = l[mid]
        if guess == x:
            return (f"count = {count}.")
        elif guess > x:
            high = mid - 1
        else:
            low = mid + 1

print(binary_search(l, x))

<<<count = 4.

Python基础练习题32：找到字符串中的第n个相同字符

给定一个字符串，里面多次出现字符'a'，如何找到第n个字符'a'的索引位置index？

解答：

def search_nth_char(s, c, n):
    """
    c: 给定要找的字符，题意是'a'。
    s: 给定要从中查找的字符串。
    n: 一个正整数int，小于等于len(s)。
    """
    l = []
    for i in range(len(s)):
        if s[i] == c:  #把原始字符串s中所有字符c的索引位置index都找出来，并放入列表l中。
            l.append(i)  
 
    return f"字符串{s}中，第{n}个字符{c}的索引位置index为{l[n-1]}。"

s = 'abcabcabc'
c = 'a'
n = 3  #第3个'a'字符串对应s的原始索引位置index为6，即第7个字符串。
print(search_nth_char(s, c, n))

<<<字符串abcabcabc中，第3个字符a的索引位置index为6。

To be continued.