二分法（又称二分查找算法）

二分查找算法讲解

枚举查找也就是顺序查找。

实现原理就是逐个比较 a[0:n-1] 中的元素，直到找出元素 x 或搜索遍整个数组后确定 x 不在其中，或者说符合要求的元素在不在数组中。

最坏的情况下需要比较 N 次，时间复杂度是 O(n) 线性阶。

二分查找也就是折半查找。折半查找是将 N 个元素分成大致相同的两部分。选取中间元素与查找的的元素比较，或者与查找条件相比较，找到或者说找到下一次查找的半区。每次都将范围缩小至1/2，所以时间复杂度是 O(log2n），但是二分查找的前提是有序的，一般是从小到排列。

在有序表中（low,high,low<=high），取中间记录即 [(high+low)/2] 作为比较对象。

若给定值与中间记录的关键码相等，则查找成功
若给定值小于中间记录的关键码，则在中间记录的左半区继续查找
若给定值大于中间记录的关键码，则在中间记录的右半区继续查找
不断重复上述过程，直到查找成功，或所查找的区域无记录，查找失败。

分巧克力

题目描述:

儿童节那天有 K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。小明一共有 N 块巧克力，其中第 i 块是 Hi×Wi 的方格组成的长方形。为了公平起见，小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。切出的巧克力需要满足：

1. 形状是正方形，边长是整数;
2. 大小相同;

例如一块 6x5 的巧克力可以切出 6 块 2x2 的巧克力或者 2 块 3x3 的巧克力。

当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？

输入描述:

第一行包含两个整数 N,K (1≤N,K≤1e5）。

以下 N 行每行包含两个整数 Hi Wi (1≤Hi,Wi≤1e5)。

输入保证每位小朋友至少能获得一块 1x1 的巧克力。

输出描述:

输出切出的正方形巧克力最大可能的边长。

输入样例

2 10
6 5
5 6

输出样例

2

题目分析:

简单思路，边长的最大规模为 100000；我们可以枚举出所有的情况。按从大到小的顺序进行切割，直到找到满足要求的巧克力边长。

在判断边长是否满足条件时：求一块长方形（h * w）最多被分成的正方形（len * len）巧克力个数为：

cnt = (h / len) * (w / len)

代码:

def check(d):
    global w,h
    res = 0
    for i in range(len(w)):
        res += (w[i]//d) * (h[i]//d)
    if res >= k:  
    	return True
    return False
n,k = map(int,input().split())
w = []
h = []
for i in range(n):
    a,b = map(int,input().split())
    w.append(a)
    h.append(b)
L ,R = 1, 100000
while L < R:
    mid = (L+R)//2
    if check(mid):  
    	L = mid +1
    else :          .
    	R = mid
print(L-1)//即输出中值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

M 次方根

题目描述:

小A最近在学高等数学，他发现了一道题，求三次根号下27。现在已知，小 A 开始计算，1 的三次方得1，2 的三次方得 8，3 的三次方得 27，然后他很高兴的填上了 3。

接着他要求 5 次根号下 164。然后他开始 1 的三次方得 1，2 的三次方得 8，3 的三次方得27…

直到他算到了秃头，也没有找到答案。

这时一旁的小 B 看不下去了，说这题答案又不是个整数。小 A 震惊，原来如此。作为程序高手的小 A，打算设计一个程序用于求解 M 次跟下N的值。

但是由于要考虑精度范围，答案必须要保留 7 位小数，连三次根号下 27 都要掰手指的小 A 又怎么会设计呢。请你帮小 A 设计一个程序用于求解 M 次根号 N。

数据范围：

1<= N <= 1e5
1<= M <= 100
且 M<N

输入描述:

第一行输入整数 N 和 M，数据间用空格隔开。

输出描述:

输出一个整数，并保留 7 位小数。
输入样例：

27 3

输出样例：

3.000000

题目分析

根据前面的知识，我们要找到一个具有单调性的数列，去二分。这个题的关键是我们要去二分什么，这里可以二分的是 a^M 中的 a，所以我们要先想办法设计出用于处理实数二分的代码。

代码:

n = 0.0
m = 0
l = 0.0
r = 0.0
mid = 0.0

eps = 0.00000001


def pd(a, m):
  c = 1.0
  cnt = int(m)

  while cnt > 0:
      c = c * a
      cnt -= 1

  if c >= n:
      return True

  else:
      return False


if __name__ == '__main__':

  n, m = input().split()

  l = 0
  r=n=int(n)

  while l + eps < r:

      mid = (l + r) / 2

      if (pd(mid, m)):
          r = mid

      else:
          l = mid

print("%.7f" % l)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

一元三次方程求解

代码:

n = input().split()
a,b,c,d = eval(n[0]),eval(n[1]),eval(n[2]),eval(n[3])
def y(x):    
    return a*x*x*x+b*x*x+c*x+d
for i in range(-100,100):
    left=i
    right=i+1
    y1=y(left)
    y2=y(right)
    if y1==0:
        print("{:.2f}".format(left),end=" ")
    if y1*y2<0 :
        while (right-left) >= 0.001:    #eps=0.001
            mid = (left+right)/2
            if y(mid)*y(right) <=0:
                left = mid
            else:
                right = mid
        print("{:.2f}".format(right),end=" ")
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19