二分法

简单二分法1. 什么是二分法二分法（Binary Search）是一种常用的查找算法，也称为折半查找。

它的原理很简单，通过将查找范围不断缩小，最终找到目标元素或确定目标元素不存在。

二分法的应用广泛，包括在查找有序数列、旋转有序数列中的元素、判断一个数的开方等方面。

2. 二分法的基本思想二分法的基本思想是将查找范围不断地二等分，然后确定目标元素可能存在的一侧。

在每次二等分之后，通过比较目标元素和中间元素的大小关系，可确定下一次二分的方向，并缩小查找范围。

3. 二分法的递归实现3.1 算法步骤1.确定查找范围的起始位置start和结束位置end，初始时start为0，end为数列长度减1。

2.计算查找范围的中间位置mid，可以使用公式mid = (start + end) // 2进行计算。

3.当start大于end时，表示查找范围为空，即目标元素不存在。

此时返回-1或其他特定值作为查找失败的标志。

4.比较中间位置mid的元素与目标元素的大小关系：–如果中间位置的元素等于目标元素，则直接返回mid，表示找到目标元素。

–如果中间位置的元素大于目标元素，则说明目标元素可能存在于左半边，将查找范围缩小到[start, mid-1]，并递归调用二分法。

–如果中间位置的元素小于目标元素，则说明目标元素可能存在于右半边，将查找范围缩小到[mid+1, end]，并递归调用二分法。

5.重复步骤2到步骤4，直到找到目标元素或确定目标元素不存在。

3.2 递归实现代码示例（Python）def binary_search_recursive(arr, target, start, end):if start > end:return -1mid = (start + end) // 2if arr[mid] == target:return midelif arr[mid] > target:return binary_search_recursive(arr, target, start, mid-1) else:return binary_search_recursive(arr, target, mid+1, end)4. 二分法的迭代实现4.1 算法步骤1.确定查找范围的起始位置start和结束位置end，初始时start为0，end为数列长度减1。

二分法
二分法是用计算机求解多项式方程时常用的一种方法．其基本思想是：若f （x 1）与f （x 2）的符号相反，则方程f （x ）＝0在区间（x 1，x 2）至少有一个根．取x 1和x 2的中点2
)(211x x r ＋＝，将区间分为两半，然后比较f （r 1）与f （x 1）的符号，若符号相同，则根必在（r 1，x 2）之间，否则在（x 1，r 1）之间．这样每作一次二分法，含根区间恰好缩小一半．不断重复二分过程无限多次时，含根区间将缩为一点，显然这是不可能的．但是有一点是可以肯定的，即每重复二分一次，所得的中点ROOT 与根的距离便会越近．不断重复二分，便会构造出一系列的中点ROOT 1，ROOT 2，…，ROOT n ，当某个中点ROOT n 与根的距离小于规定的误差ξ
0时，该ROOT n 。

就是所解方程的近似解．。

练习： 求方程x3－2x－5＝0在区间(2,3)内的实根， 取区间中点x0＝2.5，那么下一个有根区间 是________． 解 析 ： 设 f(x) ＝ x3 － 2x － 5 ， f(2)<0 ， f(3)>0，f(2.5)>0即f(2)f(2.5)<0，所以 下一个区间是(2,2.5)． 答案：(2,2.5)
2.375 2.5 - + 2.375 2.4375
f(2.375)<0,f(2.5)>0 (2.375,2.5）
f(2.375)<0,f(2.4375)>0 3 (2.375,2.4375)
|2.4375-2.375|=0.0625<0.1
方程的近似解为2.375
二分法概念 二分法定义：对于区间[a,b]上连续不断、且
知识探究
思考2:为了缩小零点所在区间的范围，接下 来应做什么？ 求区间的中点c，并计算f(c)的值
思考3:若f(c)=0说明什么？若f(a)·f(c)<0 或f(c)·f(b)<0 ，则分别说明什么？ 若f(c)=0 ，则c就是函数的零点； 若f(a)·f(c)<0 ，则零点x0∈(a,c)； 若f(c)·f(b)<0 ，则零点x0∈(c,b).
• 每查一次，可以把待查的线路长度缩减一半，算一 算，要把故障可能发生的范围缩小到50～100 m左 右，即一两根电线杆附近，要查多少次？ • 据初中所学知识可知只要7次就够了．
二分法举例 求 x2-2x-1=0 的一个正的近似解
（精确度0.1）
2-2x-1 y = x y
2.25 2.375
2.5
a
x* b x
解.
3.计算f(0.5)=-0.625;

二分法在个案中的运用方法和技巧
二分法运用方法和技巧
数学定义:二分法(Bisectionmethod)即一分为二的方法.设[a,b]为R的闭区间.逐次二分法就是造出如下的区间序列([an,bn]): a0=a，b0=b,且对任一自然数n,[an+1,bn+1]或者等于[an,cn],或者等于[cn,bn]，其中cn表示[an,bn]的中点。

典型算法:
算法:当数据量很大适宜采用该方法。

采用二分法查找时，数据需是排好序的。

基本思想:假设数据是按升序排序的，对于给定值key,从序列的中间位置k开始比较,如果当前位置ar[k]值等于key,则查找成功;
若key小于当前位置值arr[k],则在数列的前半段中查
找,ar[low,mid-1];若key大于当前位置值ar[k]，则在数列的后半段中继续查找ar[mid+1,high]。