二分查找模板

二分法模板
链接：

• 循环条件到底哪一个？
	• start <= end
	• start < end
	• start + 1 < end
• 指针变换到底哪一个
	• start = mid
	• start = mid + 1
	• start = mid - 1

弄不好就死循环，弄不好边界就失误
 
例：nums = [1,1], target = 1
使用start < end 会出现死循环

模板：
def bin_search(nums, target):
    if not nums or target < nums[0] or target > nums[-1]:
        return -1
 
    left = 0
    right = len(nums) - 1
    while left + 1 < right:      # 统一都用 <
        mid = left + (right - left)//2
        if target > nums[mid]:    # 左边界> 右边界>=
            left = mid            # 永远不动，全文通用
        elif target < nums[mid]:
            right = mid           # 永远不动，全文通用
        else:
            return mid            # 等号可以合并到 < 或 > 也可以单独考虑
 
    if nums[right] == target:
        return right
    if nums[left] == target:
        return left
 
    return -1                     # 较小的left，较大的righ
		
总结：
1.判断是返回left，还是返回right
     因为我们知道最后跳出while (left + 1< right)循环条件是left+ 1 == right。
     最后left 和right一定是卡在"边界值"的左右两边
     以数组{1, 2, 3, 3, 4,5}为例，
     如果需要查找第一个等于或者小于3的元素下标，我们比较的key值是3，则最后left和right需要满足以下条件：
     left——>2, right ——>3
     我们比较的key值是3，所以此时我们需要返回left。

    所以，最后只需要判断left或right是否等于target即可。
2.判断出比较符号
     左边界附近都是>
     右边界附近都>=

————————————————
模板讲解：
模板套用练习题1：
二分查找（倍增法）：
模板套用练习题2：


倍增:
二分查找（倍增法）：

首先特判一下首个元素. 然后设定 idx = 0 为查找的下标, jump = 1 为向后跳跃的长度.

每次循环将 idx 向后移动 jump 个元素, 并将 jump 翻倍. 而如果移动后的位置不小于 target, 则 jump 缩小至一半.

即我们在保证每次跳跃后的 idx 的位置都小于target的前提下, 倍增式地跳跃, 以此保证 O(logn) 的时间复杂度.

循环终止的条件就是 jump == 0, 就是说, 这时 idx + 1 的位置以及不小于 target 了 (此时idx位置的仍然是小于target)

也就是说, 到最后idx指向的元素是: 最大的小于target的元素. 返回答案前判断一下 idx + 1 是否 target 即可.
————————————————

辗转相除法：
 又名欧几里德算法， 是求最大公约数的一种方法。它的具体做法是：用较大的数除以较小的数，再用除数除以出现的余数（第一余数），再用第一余数除以出现的余数（第二余数），如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。
 
 def gcd(big, small):
    if small != 0:
        return gcd(small, big % small)
    else:
        return big

————————————————

快速幂算法
计算x的n次方， 即计算x^n。

由公式可知： x^n = x^{n/2} * x^{n/2}。

如果我们求得x^{n/2}， 则可以O(1)求出x^n, 而不需要再去循环剩下的n/2次。

以此类推，若求得x^{n/4}， 则可以O(1)求出x^{n/2}
 。。。。
因此一个原本O(n)的问题，我们可以用O(logn)复杂度的算法来解决。

递归版本的快速幂算法
def power(x, n):
    if n == 0:
        return 1
    
    if n % 2 == 0:
        tmp = power(x, n // 2)
        return tmp * tmp
    else:
        tmp = power(x, n // 2)
        return tmp * tmp * x

非递归版本
def power(x, n):
    ans = 1
    base = x
    while n > 0:
        if n % 2 == 1:
            ans *= base
        base *= base
        n = n // 2
    return ans
————————————————

斐波那契数列-求第n项
非递归版
def fibonacci(n):
    res = [0, 1]
    while len(res) <= n:
        res.append(res[-1]+res[-2])
    return res[n]

递归版
def fibonacci(n):
    if n == 0:
        return 0
    if n == 1 or n == 2:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)
题型参见：

二分法应用——搜索旋转数组，以前一直在纠结a[0],a[-1],a[mid], target三者关系，其实最简单的还是使用2次二分，先找到旋转数组peak，然后用正常的二分搜索即可！  

62 · 搜索旋转排序数组

描述

给定一个有序数组，但是数组以某个元素作为支点进行了旋转(比如，0 1 2 4 5 6 7 可能成为4 5 6 7 0 1 2)。给定一个目标值target进行搜索，如果在数组中找到目标值返回数组中的索引位置，否则返回-1。你可以假设数组中不存在重复的元素。

背完这套刷题模板，真的不一样！

样例

样例 1：

输入：

数组 = [4, 5, 1, 2, 3]
target = 1

输出：

2

解释：

1在数组中对应索引位置为2。

样例 2：

输入：

数组 = [4, 5, 1, 2, 3]
target = 0

输出：

-1

解释：

0不在数组中，返回-1。

挑战

O(logN) 时间限制

from typing import (
List,
)
 
class Solution:
"""
@param a: an integer rotated sorted array
@param target: an integer to be searched
@return: an integer
"""
def search(self, a: List[int], target: int) -> int:
# write your code here        
def find_peak():
l, r = 0, len(a) - 1
while l < r - 1:
mid = (l + r) >> 1
if a[mid] > a[0]:
l = mid
else:
r = mid
 
if a[l] < a[r]:
return r
return  l
 
def bin_search(l, r):            
while l < r - 1:
mid = (l + r) >> 1
if a[mid] < target:
l = mid
else:
r = mid
 
if a[l] == target:
return l
if a[r] == target:
return r
 
return -1
 
if not a:
return -1       
 
if a[0] <= a[-1]:
return bin_search(0, len(a)-1)
 
peak = find_peak()    <br>        #在前半段搜索    
if a[0] <= target <= a[peak]:
return bin_search(0, peak)
<br>        #在后半段搜索
return bin_search(peak+1, len(a)-1)

逻辑非常简单清晰！！！不要再去用以前那种复杂的解法了。。。几个关系给你整蒙逼！！！

比如下面这种，就是用到夹逼的思想：

从两边不断靠近target的值。

class Solution:
"""
@param A: an integer rotated sorted array
@param target: an integer to be searched
@return: an integer
"""
def search(self, A, target):
if not A:
return -1
 
start, end = 0, len(A) - 1
while start + 1 < end:
mid = (start + end) // 2
if A[mid] >= A[start]:
if A[start] <= target <= A[mid]:
end = mid
else:
start = mid
else:
if A[mid] <= target <= A[end]:
start = mid
else:
end = mid
 
if A[start] == target:
return start
if A[end] == target:
return end
return -1

if A[mid] >= A[start]:
if A[start] <= target <= A[mid]: ==》表示在左半边升序部分<br>            <br>            else: if A[mid] <= target <= A[end]:==》表示在右半边升序部分<br><br>要求逻辑分析非常严谨。。。<br><br><br><br>

辗转相除法的证明  

描述

给出两个整数 a 和 b，请计算 a 和 b 的最大公约数，通过 print 语句输出。

样例

评测机将通过执行命令 python main.py {a} {b} 来执行你的代码，并将 a 和 b 作为命令行参数传入。

样例一

当 a = 15， b = 12 时，程序执行打印出的结果为：

3

样例二

当 a = 10， b = 7 时，程序执行打印出的结果为：

1

挑战

你可以用时间复杂度比 O(n) 更小的方法来解决该问题吗？

import sys
 
a = int(sys.argv[1])
b = int(sys.argv[2])
# write your code here
# please print the greatest common divisor of a and b
 
def gcd(a, b):
if a % b == 0:
return b
return gcd(b, a % b)
 
print(gcd(a, b))

如何证明辗转相除法的正确呢？？？

我自己想到的一个思路，假设a，b的最大公约数是k，则有a=mk, b=nk;当然，m<n

为了找到k，采用mk%nk=?k，?肯定是小于n的，如果能够使用迭代算法，让？=1，则两个求余结果就是k，也就是要找的最大公约数了。

好，迭代如下：

mk%nk=?k

nk%?k=??k

?k%??k=???k

??%???k=....

则?一直迭代下去肯定会为1。因为两个不断变小的整数相除求余一定会迭代终止，终止条件势必被除数是1.