从零开始算法之路 ---- 35. 搜索插入位置

男娘i 2021-10-15 22:57 183阅读 0赞

**前言**:小白入门题解，算法大佬可以直接跳过此博客（大佬轻喷哈）  
**题源:** 力扣(LeetCode）[https://leetcode-cn.com/problems/search-insert-position/][https_leetcode-cn.com_problems_search-insert-position]  
**题目描述:**

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

**示例 1:**  
 输入: \[1,3,5,6\], 5  
 输出: 2

#### 解决方案一：C++ 版 迭代实现二分查找（二分搜索） ####

**思路：** 利用二分搜索查找目标元素位置，找到返回索引，如果没找到，在没找到的位置插入目标元素，返回该位置即可。  
**代码：**

class Solution { 
    public:
        int searchInsert(vector<int>& nums, int target) { 
           int left = 0, right = nums.size()-1, medium;
    		// 迭代实现二分查找
    		while(left <= right){ 
    			medium = (left + right)/2;
    			if(target < nums[medium]) right = medium - 1;
    			else if(target > nums[medium]) left = medium + 1;
    			else 
    			    //如果找到返回索引 
    		    	return medium;
    		} 
    		//如果没找到则利用 vector 的insert() 函数在 [nums.begin() + left] 位置插入该元素，返回索引 
            nums.insert(nums.begin() + left, target);
    		return left;           
        }
    };

#### 解决方案一：java 版 迭代实现二分查找（二分搜索） ####

**思路：** 和上面一样，有一点区别是 c++ 利用 vector 的 insert() 函数可以直接 在指定位置插入目标元素，但是 java 的数组没有这个函数，所以要想解决这个问题，那只能在创建一个新数组，新数组长度 = 旧数组长度 + 1，在把旧数组里面的元素复制到新元素里面。根据指定位置之后的数组元素往后移一位。再把指定的元素插进去。再把新数组赋给旧数组。  
**代码：**

class Solution { 
        public int searchInsert(int[] nums, int target) { 
            int left = 0, right = nums.length - 1, medium;
    	    // 实现二分查找
    	    while(left <= right) { 
    	    	medium = (left + right)/2;
    	    	if(target > nums[medium]) 
    	    		left = medium + 1;
    	    	else if(target < nums[medium]) 
    	    		right = medium - 1;
    	    	else
    	    		return medium;  // 搜索成功，返回目标元素索引
    	    }
    	    // 目标元素不在数组中, 新建一个数组,长度 为 nums.length + 1
    	    int[] newArray = new int[nums.length + 1];
    	    // 把旧数组的值赋给新数组
    	    for(int i = 0; i < nums.length; i++)
    	    	newArray[i] = nums[i];
    	    // 把目标元素插入新数组中
    	    for(int i = newArray.length-1; i > left; i--)
    	    	// 相当于是把旧数组的值往后挪了一个位置，直到要插入目标元素的位置 left
    	    	newArray[i] = newArray[i-1];
    	    // 在目标元素的位置 left 插入 target
    	    newArray[left] = target;
    	    // 使旧数组的指向新数组的堆内存
    	    nums = newArray;	  
    	    // 返回插入目标元素的位置 left
    		return left;                
        }
    }

#### 解决方案二：C++ 版 递归实现二分查找（二分搜索） ####

**思路：** 思路和C++ 版迭代实现没多大差别，区别只是用迭代实现二分查找还是递归实现二分查找。  
**代码：**

class Solution { 
    public:
        int searchInsert(vector<int>& nums, int target) {    	
        	int left = 0, right = nums.size()-1;
    		// 实现二分查找 
    	    return binarySearch(nums, target, left,  right);
           
        }
        // 二分查找函数 
        int binarySearch(vector<int> &nums, int target, int left, int right){ 
    		int medium =  (left + right)/2;
    		if(left <= right){ 
    			//medium = (left + right)/2;
    			// 如果目标小于中间值则去数组左边寻找 
    			if(target < nums[medium]){ 
    				medium = binarySearch(nums, target, left, medium - 1);			
    			}else if(target > nums[medium])
    				medium = binarySearch(nums, target, medium + 1, right);		 			
    		} 
    		// 用递归实现二分查找，找到目标元素 left <= right, 否则 left > right
    		if(left <= right)
    			// 搜索到目标元素返回索引 
    	    	return medium;	
    	    else{ 
    	    	// 没有搜索到目标元素的，按顺序插入该元素并返回插入位置
    	    	nums.insert(nums.begin() + left, target);
    			return left;    			 
    		}
    		 
    	} 
    };

#### 解决方案二：Java 版 递归实现二分查找（二分搜索） ####

**思路：** 思路和 Java 版迭代实现没多大差别，区别只是用迭代实现二分查找还是递归实现二分查找。  
**代码：**

class Solution { 
        public int searchInsert(int[] nums, int target) { 
    	    int left = 0, right = nums.length - 1;
    	    return binarySearch(nums, target, left, right);
    	}
    	
    	// 递归实现二分查找
    	public int binarySearch(int []nums, int target, int left, int right) { 
    		int medium = (left + right)/2;
    		if(left <= right) { 
    			if(target < nums[medium])
    				medium = binarySearch(nums, target, left, medium - 1);
    			else if(target > nums[medium])
    				medium = binarySearch(nums, target, medium + 1, right);
    		}
    		// 用递归实现二分查找，找到目标元素 left <= right, 否则 left > right
    		if(left <= right)
    			return medium;
    		else { 
    			// 没有搜索到目标元素的，按顺序插入该元素并返回插入位置
    			// 目标元素不在数组中, 新建一个数组,长度 为 nums.length + 1
    		    int[] newArray = new int[nums.length + 1];
    		    // 把旧数组的值赋给新数组
    		    for(int i = 0; i < nums.length; i++)
    		    	newArray[i] = nums[i];
    		    // 把目标元素插入新数组中
    		    for(int i = newArray.length-1; i > left; i--)
    		    	// 相当于是把旧数组的值往后挪了一个位置，直到要插入目标元素的位置 left
    		    	newArray[i] = newArray[i-1];
    		    // 在目标元素的位置 left 插入 target
    		    newArray[left] = target;
    		    // 使旧数组的指向新数组的堆内存
    		    nums = newArray;	  
    		    // 返回插入目标元素的位置 left
    			return left;
    			
    		}
    	}
    }

[https_leetcode-cn.com_problems_search-insert-position]: https://leetcode-cn.com/problems/search-insert-position/