递归

递归的算法

解决的问题

类似剥洋葱，每次操作类似，但是问题的规模变小了

只需要考虑：

• 当前层和里面一层的关系

  即递归的拆解

• 最里层的实现的情况

  即递归的出口

递归三要素

1. 递归的定义：入参、出参、代表的意思

2. 递归的拆解：

   一定要确保每次问题规模缩小，否则会无限递归

3. 递归的出口：

使用递归来写二分法

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);
}

非递归二分法

无重复数，或者有重复则随便返回一个时：

public int findPosition(int[] nums, int target) {
    if (nums == null || nums.length == 0) {
        return -1;
    }
    
    int start = 0, end = nums.length - 1;
    while (start < end) {
        int mid = start + (end - start) / 2;
        if (nums[mid] == target) {
            return mid;
        }
        if (nums[mid] < target) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    
    return -1;
}

返回最后一个 && 找比target大的最左的一个数

要素

1. start + 1 < end，避免死循环（最后一个位置）
2. 退出以后是两个数，需要判断，注意次序
3. 有时mid这里会被挑刺，都进阶int32最大时，则变成 start + (end-start)/2
4. 可以不加1，不减1

public int findPosition(int[] nums, int target) {
    if (nums == null || nums.length == 0) {
        return -1;
    }
    
    int start = 0, end = nums.length - 1;
    while (start + 1 < end) {
        int mid = start + (end - start) / 2;
        if (nums[mid] == target) {
            start = mid;
        }
        if (nums[mid] < target) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    
    if (nums[end] == target) {
        return end;
    }
    
    if (nums[start] == target) {
        return start;
    }
    
    return -1;
}

返回第一个 && 找比target小的最右的一个数

public int findPosition(int[] nums, int target) {
    if (nums == null || nums.length == 0) {
        return -1;
    }
    
    int start = 0, end = nums.length - 1;
    while (start + 1 < end) {
        int mid = start + (end - start) / 2;
        if (nums[mid] == target) {
            end = mid;
        }
        if (nums[mid] < target) {
            start = mid; //可以这样偷懒，因为这样也会退出
            // start = mid + 1;
        } else {
            end = mid; //可以这样偷懒，因为这样也会退出
            // end = mid - 1;
        }
    }
    
    if (nums[start] == target) {
        return start;
    }
    
    if (nums[end] == target) {
        return end;
    }
    
    return -1;
}

如果没target，求比target最大的小一些的位置

二分法是减治（Decrease and Conquer）算法的思想