递归&二分法_二分法递归

1. 用T函数表示法计算时间复杂度

例如二分法 T(n) = T(n/2) + O(1)，将规模为n的问题降低为规模为n/2的问题

1）首先 T 代表的是 Time Complexity,n 代表的是问题规模（二分法里就是数组的大小）。
那么 T(n) 代表的就是：求处理问题规模为n的数据的时间复杂度是多少。

2）然后 O 代表的是时间复杂度。O(1) 就意味着，你大概用一个 if 语句，或者简单的加加减减，就可以完成。O 在这里的意思是数量级约等于。在 O 的世界里，我们只考虑最高项是什么，不考虑系数和常数项。

2. 递归 （从后往前推导，降低所给问题的规模）

1）递归的三要素

• 递归的定义：函数接受什么样的参数，返回什么样的值，代表什么样的意思
• 递归的拆解
• 递归的出口

2）Stack Overflow

摘要：我们通常所说的内存空间，包含了两个部分：栈空间 (stack space) 和 堆空间 (heap space)

栈空间 (Stack space)：当一个程序在执行的时候，操作系统为了让进程可以使用一些固定的、不被其他进程侵占的空间用于函数调用、递归等操作，会开辟一个固定大小的空间 (比如8M) 给进程使用。这个空间通常不会太大，否则内存的利用率会很低，这个空间就是我们所说的 Stack space。

栈空间里存储的内容，会在函数执行结束的时候被销毁。

栈空间主要包含：

• 函数的参数与返回值
• 函数的局部变量

堆空间 (Heap space)：通常对象、new出来的东西都会存放在堆空间中。堆空间里存放的内容在函数执行结束后不会被销毁。

stack overflow: 我们通常所说的栈溢出，是指在函数调用或递归调用时，开辟了过多的内存，超出了操作系统分配的那个很小的固定空间导致的。

3）递归深度

定义：递归深度就是递归函数在内存中，同时存在的最大次数。

函数的调用，会在内存的栈空间中开辟新空间，用来存放子函数。递归函数会不断占用栈空间，因而太深的递归会导致栈空间溢出。

3. 二分法

1）基本原理：

每次取数组当前区间的中点，并与目标值target比较，根据比较结果缩减一半搜索范围，时间复杂度为O(logn)

2）基本条件：有序数组

3）递归实现：

class Solution {
    public int search(int[] nums, int target) {
        return binarySearch(nums,0,nums.length-1,target);
    }
 
    // 通过缩减区间，来达到降低问题规模的目的
    private int binarySearch(int[] nums, int start, int end, int target){
        // 递归出口
        if(start > end){
            return -1;
        }
 
        int mid = start + (end - start)/2;
        if(nums[mid] == target){
            return mid;
        }
        if(nums[mid] < target){
            return binarySearch(nums,mid+1,end,target);
        }
        return binarySearch(nums,start,mid-1,target);
    }
}

4）非递归-无死循环实现：

public class Solution {
    /**
     * @param A an integer array sorted in ascending order
     * @param target an integer
     * @return an integer
     */
    public int findPosition(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
 
        int start = 0, end = nums.length - 1;
        // 要点1: start + 1 < end
        while (start + 1 < end) {
     // 要点2：start + (end - start) / 2
            int mid = start + (end - start) / 2;
            // 要点3：=, <, > 分开讨论，mid 不+1也不-1
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }
 
        // 要点4: 循环结束后，单独处理start和end
        if (nums[start] == target) {
            return start;
        }
        if (nums[end] == target) {
            return end;
        }
        return -1;
    }
}

注： 为什么while条件要写成start + 1 < end ?

意味着当数组区间中剩余2个数时，退出循环。因为在某些情况下 --- 寻找最右数，会陷入死循环

例如[1,1] target = 1，取中点并与target比较后，区间范围依然是[1,1]，没有缩小，导致代码超时。

4. 相关例题

leetcode: 509. 斐波那契数，704. 二分查找，34. 在排序数组中查找元素的第一个和最后一个位置，剑指 Offer II 069. 山峰数组的顶部