python编程 ：第二十六课：让查找更“聪明” – 基础查找算法与排序回顾

• 时长: 90 分钟
• 教学目标:
  • 理解“查找”的基本概念：在一组数据中找到目标元素。
  • 学习顺序查找（线性查找）的算法思想和实现：从头到尾依次比较。
  • 了解顺序查找的优缺点和适用场景。
  • 回顾并深入列表的排序方法 (.sort() 和 sorted())，理解排序对查找的重要性。
  • 初步了解二分查找（Binary Search）的算法思想（前提是数据必须有序），体会它比顺序查找更快的效率（无需编写代码实现，主要讲解思想）。
  • 练习结合循环、条件判断和函数，实现简单的查找功能。
  • 培养对算法效率的初步感知。

课程内容

1. 复习与引入 (10 分钟)

• 复习: 快速回顾 os 模块在文件查找中的应用，以及列表、字典、函数、循环和条件判断。
• 提出问题: 老师提问：“我们之前学过如何在列表中检查一个元素是否存在（用 in 运算符），也学过如何用 index() 找元素的位置。那这些查找是怎么进行的呢？比如，老师有一个班级的点名册（列表），里面有 50 个同学的名字。我怎么快速找到‘小明’同学的名字在第几个位置？如果点名册是乱序的，又或者它是按拼音排好序的，找起来会一样快吗？”
• 引出查找算法: 这就涉及到“查找”的算法了。查找是在一组数据中找到目标元素的过程。不同的查找方法，效率可能会天壤之别。今天我们先从最简单、最直观的查找方法学起，并看看排序如何帮助我们查找。

2. 最直接的查找 – 顺序查找（线性查找） (20 分钟)

• 概念: 顺序查找（或称线性查找）是最简单直接的查找方法。它从数据集合的第一个元素开始，依次向后比较，直到找到目标元素，或者遍历完所有元素仍未找到。
• 算法思想:
  1. 从列表的第一个元素开始。
  2. 比较当前元素是否是我们要找的目标。
  3. 如果是，查找成功，返回当前元素的索引（或 True）。
  4. 如果不是，就看下一个元素。
  5. 重复步骤 2-4，直到所有元素都看完了。
  6. 如果所有元素都看完了还没找到，查找失败，返回一个特殊值（如 -1 或 False）。
• 用代码实现 (封装在函数中):

  # 顺序查找函数
  # list_data: 要查找的列表
  # target: 要查找的目标元素
  def linear_search(list_data, target):
      # 遍历列表中的每一个元素及其索引
      for index in range(len(list_data)):
          # 比较当前元素是否等于目标
          if list_data[index] == target:
              print(f"找到啦！'{target}' 在索引 {index} 的位置。")
              return index # 找到后立即返回索引，结束函数
  
      # 如果循环结束还没找到，说明目标不在列表中
      print(f"'{target}' 不在列表中。")
      return -1 # 返回 -1 表示未找到
  
  # --- 主程序部分 ---
  my_students = ["小明", "小红", "小刚", "小丽", "小强", "小明"]
  search_target1 = "小刚"
  search_target2 = "小芳"
  search_target3 = "小明" # 重复元素
  
  print(f"在列表 {my_students} 中查找：")
  result1 = linear_search(my_students, search_target1)
  result2 = linear_search(my_students, search_target2)
  result3 = linear_search(my_students, search_target3) # 找到第一个就返回
  
  # 实际应用中，Python 的 in 和 .index() 也是顺序查找的优化版
  print("--- Python 内置方式 ---")
  print("小丽在列表中吗？", "小丽" in my_students)
  try:
      print("小丽的索引是：", my_students.index("小丽"))
  except ValueError:
      print("小丽不在列表中（用.index()）。")
  

• 优缺点:
  • 优点: 简单易懂，代码容易实现。数据不需要有任何顺序。
  • 缺点: 效率较低。在最坏情况下（目标在最后或不存在），需要比较所有元素。如果列表很长，会非常慢。
• 动手实践: 学生编写 linear_search 函数，并用不同的列表和目标进行测试。

3. 让数据有“秩序” – 排序回顾与重要性 (20 分钟)

• 复习排序: 快速回顾列表的排序方法。
  • .sort(): 直接修改原列表，进行升序排序。

    my_numbers = [5, 2, 8, 1, 9]
    my_numbers.sort()
    print("原地升序排序后:", my_numbers) # [1, 2, 5, 8, 9]
    

  • sorted(): 不修改原列表，返回一个新的已排序的列表。

    original_numbers = [5, 2, 8, 1, 9]
    new_sorted_numbers = sorted(original_numbers, reverse=True) # 降序
    print("原始列表:", original_numbers) # [5, 2, 8, 1, 9]
    print("新降序列表:", new_sorted_numbers) # [9, 8, 5, 2, 1]
    

• 排序的重要性: 为什么我们要把数据排好序？对于查找来说，有序的数据可以让我们查找得更快！ 就像查字典，如果单词是乱序的，你只能从头翻到尾；如果按字母顺序排好了，你可以很快地找到目标。

4. 更快的查找（初步概念） – 二分查找 (Binary Search) (25 分钟)

• 核心思想 (重点！): 二分查找只适用于已经排好序的数据。它的思想是“二分法”：
  1. 首先，找到列表中间的那个元素。
  2. 将中间元素和我们要找的目标进行比较。
  3. 如果中间元素就是目标，查找成功！
  4. 如果目标比中间元素小，那么目标一定在中间元素的左边部分，我们就可以把查找范围缩小到左半部分。
  5. 如果目标比中间元素大，那么目标一定在中间元素的右边部分，我们就可以把查找范围缩小到右半部分。
  6. 然后，对缩小后的那一半数据，重复步骤 1-5，直到找到目标，或者查找范围缩小到空（表示没找到）。
• 打个比方: 就像猜数字游戏，我心里想一个 1 到 100 的数字。你第一次猜 50。如果我告诉你“小了”，你就知道数字在 51 到 100 之间。你第二次猜 75… 每次都能排除掉一半的可能。
• 优点 (与顺序查找对比): 二分查找的效率比顺序查找高得多。对于一个很长的列表，二分查找只需要很少的比较次数就能找到目标。例如，在一个有 100 万个元素的列表中，顺序查找最坏需要 100 万次，而二分查找最多只需要大约 20 次！
• 缺点: 数据必须是有序的！
• 学生无需编写代码: 对于中小学生来说，二分查找的实现略复杂，涉及循环边界的控制。本节课的目的是让学生理解它的思想和效率优势，知道“排序后的数据可以更高效地查找”。
• 演示过程: 老师可以使用板书或画图，一步步模拟二分查找的过程，让学生直观感受其效率。
  • 例如，在 [1, 5, 8, 12, 16, 23, 28] 中查找 12：
    • 中间是 12，找到了！
  • 例如，在 [1, 5, 8, 12, 16, 23, 28] 中查找 7：
    • 中间 12。 7 比 12 小，看左半边 [1, 5, 8]。
    • 中间 5。 7 比 5 大，看右半边 [8]。
    • 中间 8。 7 比 8 小，看左半边 []。
    • 范围为空，没找到。
• 动手实践: 老师可以准备一些排序好的数字卡片，让学生分组，用二分查找的步骤来“玩”找数字游戏，体验其过程。

6. 课堂练习 (10 分钟)

让学生独立完成以下练习：

• 练习 1: 编写一个程序，有一个学生成绩列表 scores = [85, 92, 78, 60, 95, 50, 88]。
  • 使用 .sort() 方法将列表进行升序排序。
  • 使用你编写的 linear_search 函数，查找分数 60 和 100 是否在这个排序后的列表中。
• 练习 2: 编写一个函数 find_first_occurrence(text_list, char)，接收一个字符串列表和一个字符作为参数。使用顺序查找，返回这个字符第一次出现在列表中哪个字符串中（返回字符串本身），如果所有字符串都不包含这个字符，则返回 None。

  def find_first_occurrence(text_list, char):
      # TODO: 遍历 text_list
      # TODO: 在每个字符串中检查 char 是否存在 (使用 in 运算符)
      # TODO: 如果存在，返回这个字符串
      # TODO: 循环结束后，返回 None
      pass
  
  my_texts = ["apple", "banana", "cherry", "date"]
  print(find_first_occurrence(my_texts, "c")) # 应该返回 "cherry"
  print(find_first_occurrence(my_texts, "z")) # 应该返回 None
  

• 练习 3: (思考题，无需代码) 你的手机通讯录里有 10000 个联系人，是按名字拼音排好序的。你想查找一个叫“张三”的人。
  • 如果用顺序查找（从第一个人开始往后翻），最坏需要翻多少次？
  • 如果用类似二分查找的方法，大概需要翻多少次？（提示：10000 大约是 2 的 13-14 次方）。

7. 总结与提问 (5 分钟)

• 回顾: 回顾本节课内容：查找的概念，顺序查找的实现和特点，排序对查找的重要性，二分查找的思想和高效性（适用于有序数据）。
• 提问:
  • 顺序查找的步骤是怎样的？它有什么优点和缺点？
  • 为什么要把数据排好序才能使用二分查找？
  • 二分查找比顺序查找快在哪儿？
  • 在 Python 中，如何给列表进行升序排序？
• 答疑: 回答学生问题。

8. 布置课后作业 (5 分钟)

• 作业 1: 编写一个函数 find_smallest(numbers)，接收一个数字列表作为参数，使用顺序查找的思想（自己写循环比较，不使用 min() 函数），找出并返回列表中最小的数字。
• 作业 2: 编写一个程序，创建一个包含 10 个英文单词的列表（可以重复）。让用户输入一个单词，然后使用你编写的 linear_search 函数查找这个单词在列表中第一次出现的位置。如果不在，提示未找到。
• 作业 3: (二分查找思想应用) 编写一个程序，模拟猜数字游戏。程序随机生成一个 1 到 100 的整数。让用户输入猜测，程序提示“猜大了”或“猜小了”，直到猜对。统计猜测次数。思考：用户在猜数字时，最快的方法是不是类似二分查找？
• 作业 4: (选做) 编写一个函数 bubble_sort(input_list)，实现冒泡排序算法（最简单的排序算法之一）。对一个列表进行升序排序。这会比直接调用 .sort() 更复杂，但能帮助理解排序算法的内部机制。