📢前言
🚀 算法题 🚀
🌲 每天打卡一道算法题，既是一个学习过程，又是一个分享的过程😜
🌲 提示：本专栏解题 编程语言一律使用 C# 和 Java 两种进行解题
🌲 要保持一个每天都在学习的状态，让我们一起努力成为算法大神吧🧐！
🌲 今天是力扣算法题持续打卡第16天🎈！
🚀 算法题 🚀
🌲原题样例
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。
如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 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
示例 4: 输入: nums = [1,3,5,6], target = 0 输出: 0
示例 5: 输入: nums = [1], target = 0 输出: 0
提示:
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 为无重复元素的升序排列数组
-104 <= target <= 104
🌻C#方法一：普通法
思路解析
这道题跟上一篇的实现 strStr()挺相似的，都是给定一个目标值，返回索引
但是这个是从数组中查找，上一个是字符串！
分析一下可能出现四种情况
nums[i]==target
nums[i]>target
nums[0]>target
nums[nums.Length-1]<target
前三种对应if(nums[i] >= target) return i;，最后一种对应：return nums.Length;
代码：
public class Solution { public int SearchInsert(int[] nums, int target) { for(int i = 0; i < nums.Length; i++) { if(nums[i] >= target) return i; } return nums.Length; } }
执行结果
通过 执行用时：76 ms，在所有 C# 提交中击败了99.07%的用户 内存消耗：24.7 MB，在所有 C# 提交中击败了44.39%的用户
复杂度分析
时间复杂度：O(long n) 空间复杂度：O(1)
🌻C#方法二：二分法
代码：
public class Solution { public int SearchInsert(int[] nums, int target) { int low = 0; int high = nums.Length - 1; int mid = 0; while (low <= high) { mid = (low + high) / 2; if (target == nums[mid]) return mid; else if (target > nums[mid]) low = mid + 1; else high = mid - 1; } //以上是常规的二分法 if (target > nums[mid]) return mid + 1; else return mid; } }
执行结果
通过 执行用时：76 ms，在所有 C# 提交中击败了99.07%的用户 内存消耗：24.5 MB，在所有 C# 提交中击败了84.00%的用户
🌻Java 方法一：二分法
代码：
class Solution { public: int searchInsert(vector<int>& nums, int target) { int n = nums.size(); int l=0,r=n-1; while(l<=r){ int mid=l+(r-l)/2; if(nums[mid]<target) l=mid+1; else r=mid-1; } return l; } };
执行结果
通过 执行用时：0ms，在所有 Java 提交中击败了100%的用户 内存消耗：37.8 MB，在所有 Java 提交中击败了87.55%的用户
复杂度分析
时间复杂度：O(long n) 空间复杂度：O((1)
💬总结
- 今天是力扣算法题打卡的第十六天！
- 文章采用
C#和Java两种编程语言进行解题 - 一些方法也是参考力扣大神写的，也是边学习边分享，再次感谢算法大佬们
- 那今天的算法题分享到此结束啦，明天再见！
