[数据结构与算法]LeetCode 35. 搜索插入位置

题目描述：?? ??

????????给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。请必须使用时间复杂度为 O(log n) 的算法。

代码示例：

示例 1:

????????输入: nums = [1,3,5,6], target = 5
????????输出: 2

示例?2:

????????输入: nums = [1,3,5,6], target = 2
????????输出: 1

示例 3:

????????输入: nums = [1,3,5,6], target = 7
????????输出: 4

解题思路：?

? ? ? ? 因为题目要求使用时间复杂度为 O(log n) 的算法，也就是二分法，所以方向很明确。在二分法中，我们可以采用循环的方式，也可以采用递归的方式，本人比较喜欢递归，所以第二次在刷这道题的时候采用的也是递归来做，老样子，采用递归最重要的就是结束递归的条件，这个是根据题目而定的，剩下的就是二分法的样板式代码了，所以只要试出了结束递归的条件，这道题就迎刃而解了。

代码实现：

class?Solution?{

????public?int?searchInsert(int[]?nums,?int?target)?{

????????if?(target?>?nums[nums.length-1])?return?nums.length;

????????return?searchInsert(nums,?target,?0?,nums.length-1);

????}

????public?int?searchInsert(int[]?nums,?int?target,?int?start,?int?end){

? ? ? ? //? 递归的结束条件，因为需要返回插入的位置，所以返回start，如果不返回插入位置

? ? ? ? //? 只要求返回-1 的话，把start改成-1即可，同时去掉程序最开始的判断条件，

????????if?(nums[start]?!=?target?&&?start?==?end)?return?start;

????????int?mid?=?start?+?(end?-?start)?/?2;

????????if?(target?==?nums[mid])?return?mid;

????????if?(target?>?nums[mid])??return?searchInsert(nums,?target,?mid?+?1,?end);

????????else?return?searchInsert(nums,?target,?start,?mid);

????}

}