Python｜二分查找（涉及递归思想）

二分查找介绍

二分查找（搜索）是一种在有序列表中查找某一特定元素的搜索算法。

首先先查找到目标列表的中间元素，如果中间元素正好是要查找的元素，则返回查找元素的索引下标，搜索结束；

如果要查找的元素大于或者小于中间元素，则在列表大于或小于中间元素的那一半中查找，并且跟开始一样从中间元素开始比较。

如果在某一步骤数组为空，则代表要查找的元素不在目标列表中。这种搜索算法每一次比较都使搜索范围缩小一半，是一方便快捷的搜索算法。

递归思想（化整为零）

由于这种搜索的整个过程可以分割成许多个相同的操作流程，所以可以运用递归思想使代码变得轻盈优雅。

递归定义（什么是递归？）

在数学与计算机科学中，递归(Recursion)是指在函数的定义中使用函数自身。

实际上，递归，顾名思义，其包含了两个意思：递和归，这正是递归思想的精华所在。

简而言之就是定义一个函数，在其中定义一个条件，满足该条件将会返回该函数函数名，即函数调用函数本身。

需要注意的是，定义的递归函数必须有明确的结束条件，否则就会导致无限递归的情况。

递归三要素

明确递归终止条件

递归就是有去有回，因此必然应该有一个明确的临界点，程序一旦到达了这个临界点，就不用继续往下递去而是开始实实在在的归来，防止无限递归。

在递归终止时提供处理办法

由于在递归函数中存在临界点，当满足临界点时，我们应该给出问题的解决方案。一般地，在这种情境下，问题的解决方案是直观的、容易的。

提取重复的逻辑，缩小问题规模

由于递归问题一定可以分解为若干个规模较小、操作流程相同的子问题，这些子问题可以用相同的解题思路来解决。

从程序实现的角度而言，我们需要抽象出一个干净轻盈的逻辑，以便使用相同的方式解决子问题。

 实例：

二分法查找：输入一个有序的元素列表（必须有序），如果要查找的元素包含在其中，二分法查找返回其位置，否则返回None。

运行结果：

当要查找的元素在目标列表中时

输入数字：26

当要查找的元素不在目标列表中时

输入数字：4561