搜索插入位置

ゝ一纸荒年。 2021-12-11 13:17 239阅读 0赞

## 题目描述 ##

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

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

示例 1:

输入: [1,3,5,6], 5
    输出: 2

示例 2:

输入: [1,3,5,6], 2
    输出: 1

示例 3:

输入: [1,3,5,6], 7
    输出: 4

示例 4:

输入: [1,3,5,6], 0
    输出: 0

## 解法 ##

1、递归二分法查找

public int searchInsert(int[] nums, int target) { 
    	if(nums.length<1) { 
    		return 0;
    	}
    	if(target<=nums[0]) { 
    		return 0;
    	}else if (target>nums[nums.length-1]) { 
    		return nums.length;
    	}
    	//二分
    	return search(nums, target, 0, nums.length-1);
       }
    
    private int search(int[] nums, int target, int start, int end) { 
    	int mid = (start+end)/2;
    	if(target == nums[mid]) { 
    		return mid;
    	}
    	if (end-start == 1) { 
    		return end;
    	}
    	
    	if (target>nums[mid]) { 
    		return search(nums, target, mid, end);
    	}else { 
    		return search(nums, target, start, mid);
    	}
    }

2、非递归二分查找

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

发表评论取消回复

表情：

评论列表（有 0 条评论，239人围观）

还没有评论，来说两句吧...

相关阅读

相关搜索插入位置

35. 搜索插入位置 > 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。 > 请必须使用时间复

清疚/ 2024年04月07日 13:48/ 0 赞/ 29 阅读

相关搜索插入位置

搜索插入位置 1、参考资料 https://leetcode-cn.com/problems/search-insert-position/ 2、题目要求

柔光的暖阳◎/ 2022年12月04日 05:24/ 0 赞/ 128 阅读

相关 35. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。你可以假设数组中无重复元素。示例 1: 输入:

川长思鸟来/ 2022年10月04日 12:55/ 0 赞/ 167 阅读

相关 35.搜索插入位置

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

短命女/ 2022年09月11日 08:13/ 0 赞/ 168 阅读

相关搜索插入位置 JavaScript

在有序数组中查找（无则插入）元素，返回索引。题目详情：[https://leetcode-cn.com/problems/search-insert-position/d

系统管理员/ 2022年05月18日 08:43/ 0 赞/ 147 阅读

相关 LeetCode——搜索插入位置

题目：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。你可以假设数组中无重复元素。示例

迷南。/ 2022年05月15日 06:09/ 0 赞/ 159 阅读

相关搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。你可以假设数组中无重复元素。示例 1:

秒速五厘米/ 2022年04月23日 08:16/ 0 赞/ 239 阅读

相关搜索插入位置

题目描述给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。你可以假设数组中无重复元素。示例

ゝ一纸荒年。/ 2021年12月11日 13:17/ 0 赞/ 240 阅读

相关搜索插入位置

题目描述：来源（[https://leetcode-cn.com/problems/search-insert-position/][https_leetcode-cn.com

约定不等于承诺〃/ 2021年12月09日 15:03/ 0 赞/ 412 阅读

相关 leetcode 搜索插入位置

题目描述给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。你可以假设数组中无重复元素。 >

清疚/ 2021年11月02日 00:02/ 0 赞/ 228 阅读