#利用演算法找出最小值(很像20161202最後一個)
def min(a,low,high): #這裡的low跟high是位置
    if low == high: #只剩最後一人
        return a [low] #寫a[high]也可以

    mid = ( low + high ) // 2 
#人數超過一人
#因為是整數索引
#所以用//
    x = min( a , low , mid )
    y = min( a , mid+1 , high )
    
    return x if x < y else y
    
#>>>a=[2,4,9,-10,1,999,0]
#>>>min(a,0,len(a)-1)
#-10
#問題本質不變
#將資料劃分為左右各一半
#減少數量
#可用遞迴
#key:分而至至，大問題化為小問題但性質不變





#快速排序法(Quicksort)
def quicksort(a):
    if len(a)<=1:
        return a
    
    return quicksort([x for x in a[1:] if x < a[0]]) +\
        [a[0]] +\
        quicksort([x for x in a[1:] if x >= a[0]])

#[1:]從編號1(第二位，因為第一個數字(編號0)拿去當標兵了)
#照理說要[1:50](最後一個不算，所以是到編號49(第50位))
#可是因為是到最後面
#所以省略50
#如果是前面都算(要第1位到第20)
#[:21]

#+/是接續的意思
#因為式子太長了
#>>> a=[2,9,5,6,5,21,5646,523,541,51314,5466,56]
#>>> quicksort(a)
#[2, 5, 5, 6, 9, 21, 56, 523, 541, 5466, 5646, 51314]

#>>> a=random.sample(range(1000000),50)
#>>> a
#[752878, 706610, 797734, 943620, 166648, 278777, 836834, 393291, 376299, 293766, 6849, 293217, 74566, 615874, 273201, 872705, 885634, 106021, 983425, 502083, 287004, 56862, 772246, 115440, 608813, 518119, 960337, 78945, 716364, 465422, 166369, 358085, 828272, 47688, 874610, 915875, 466887, 423080, 499999, 943500, 140012, 415681, 692237, 149714, 633269, 969047, 941554, 280041, 388510, 744094]
#>>> b=quicksort(a)
#>>> b
#[6849, 47688, 56862, 74566, 78945, 106021, 115440, 140012, 149714, 166369, 166648, 273201, 278777, 280041, 287004, 293217, 293766, 358085, 376299, 388510, 393291, 415681, 423080, 465422, 466887, 499999, 502083, 518119, 608813, 615874, 633269, 692237, 706610, 716364, 744094, 752878, 772246, 797734, 828272, 836834, 872705, 874610, 885634, 915875, 941554, 943500, 943620, 960337, 969047, 983425]
#>>> c=sorted(a)
#>>> b==c
#True

#挑一個人當標兵
#比標兵矮的在左邊
#比標兵高的在右邊
#因為左邊跟右邊是沒有順序的
#因此左邊跟右邊用相同方法
#繼續快速排列





#Bisection Method(典型的二分法)
#選定一個區間
#因為conti.
#所以一正一負
#中間必有解
#即一個函數求解
#同正或同負就拋棄
def bisection(f,x1,x2,e = 1e-6):
    y1=f(x1)
    
    while x2 - x1 > e:
        x = (x1 + x2) / 2.0
        y = f(x)
        
        if y * y1 >0:
            x1 = x
        else:
            x2 = x
    return x
        
#Python把函數當參數傳回
#e代表誤差值
#1e的 e是指(10的n次方)
#1e-6 = 10的-6次方
#兩個 e不一樣
#浮點數用以科學記號表示法
#浮點數用/(一條斜線)
#x的位置(x1-->x-->x2)
#所以當y*y1>0時
#x右移

#>>> x=bisection(lambda x : x**2-3*x+2,0,1.5)
#>>> print('{:.3f}'.format(x))
#1.000

#>>> x=bisection(lambda x : x**2-3*x+2,1.5,3)
#>>> print('{:.3f}'.format(x))
#2.000

#lambda funcion是臨時函數
#":"後可直接寫你要用的式子