二分查找

1. 最简单的二分查找有什么用##

对于一个有序数列，查找某一个特定值。

```
def binary_search(a, target):
    """
    a:list
    target:int
    """

    l = 0
    r = max(a)
    while l < r:
        mid = (l + r) >> 1
        if a[mid] == target:
            return mid
        if a[mid] > target:
            r = mid - 1
        else:
            l = mid + 1
    return -1
```

二分查找需要保持数组的有序性###

如果无序呢？

可以先排序

如果求第k大数

可以用快排的思想

2. 复杂一些的呢##

一个复杂一些的问题：
给出一个有序数组，然后有序数组循环移动了k位，然后问target存在不存在。

例如a = [1,2,3,4,5,6,7,8,9],k = 3 则给定的输入为：a = [7,8,9,1,2,3,4,5,6], target = 5，使用O(1)的额外空间复杂度完成。

假设可以用额外的空间，那么效率是多少？ O(n) + O(logn)

太慢了，有没有更快的呢？

通过观察，其实数组仍然是有序的，如果k已知那么直接分成两个部分解决即可，but 目前你并不知道k=？

```
int search(vector<int>& nums, int target) {
    int l=0,r=nums.size()-1;
    while(l<=r)
    {
        int mid=(r+l)/2;
        if(nums[mid]==target)return mid;
        if(nums[l] < nums[mid])
        {
            if(nums[mid]>target && target>=nums[l])r=mid-1;
            else l=mid+1;
        }else if(nums[l] > nums[mid])
        {
            if(target>nums[mid] && target <= nums[r])l=mid+1;
            else r=mid-1;
        }else l++;
    }
    return -1;
}
```

关键在于判断前一半有序还是后一半有序，如果nums[l] < nums[mid]则说明前一半有序,如果nums[l] > nums[mid]则说明后一半有序，然后只需要判断target是否夹在有序子序列的中间即可，最后如果nums[l] = nums[mid]说明有情况a = [5,5,5,1,2,3,4,5,5,5,5,5,5]无法判断前后哪个有序，那么l++即可。

思考题

给定两个有序数组a,b.查找a,b合并后的第k小数,重复元素分别算.

例如 a = [2,4,6,8], b = [1,3,5,7], k = 3；返回值为3

朴素的想法是O(n + m)的时间复杂度，那么有没有log(n) + log(m)的呢？

3. 迭代逼近-求多项式的解##

给定一元n次方程组，f(x)=a1x^1 + a2x^2 + a3x^3 + ··· + anx^n = 0,求x的解。

首先可以先找到一个另f(x) < 0的x1，再找到一个另f(x) > 0的x2，然后让l=x1,r=x2使用二分查找逼近x的解。

mid = (l + r) / 2.0;
if (abs(f(mid)) < 1e-8) return mid;
else if (f(mid) < 0) l = mid;
else r = mid;

4. 迭代逼近2-求解判定性问题##

求解判定性问题,leetcode410. Split Array Largest Sum 既判定一个给定的解是否能解决该问题。

public class Solution {
    public int splitArray(int[] nums, int m) {
        long l = Integer.MAX_VALUE, r = 0, ret = Integer.MAX_VALUE;
        for(int i=0;i<nums.length;i++) {
            r += nums[i]; 
            l = Math.min(l, nums[i]);
        }
        while (l <= r) {
            long mid = (l + r) >> 1;
            long tmp = 0, k = 1, max = 0;
            for (int i=0;i<nums.length;i++) {
                tmp += nums[i];
                if (tmp > mid) {
                    if (nums[i] > mid) {
                        k = m + 1;
                        break;
                    }
                    tmp = nums[i];
                    k++;
                    if (k > m) break;
                } else {
                    max = Math.max(tmp, max);
                }
            }
            max = Math.max(tmp, max);
            
            if (k > m) {
                l = mid + 1;
            }else {
                r = mid - 1;
                ret = Math.min(ret, max);
                
            }
        }
        
        return (int)ret;
    }
}