35.搜索插入位置

问题类型： Easy
喜欢： 14.6k
不喜欢： 630

公司问了这个问题：

公司名称：否时代
亚马逊4
Google 2
苹果8
微软5
Adobe 4
雅虎2
彭博2
Facebook 7
VMware 5
Uber 4
LinkedIn 2
Teltok 2
TCS 2

给定一个不同的整数和target值的array，如果找到目标，请返回index。如果不是，请返回index如果将其插入order。

您必须使用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

约束：

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums包含不同的值上升顺序。
-104 <= target <= 104

方法：

初始化指针：
初始化两个指针，即启动和结束，以表示排序的数组中的搜索范围。启动最初指向第一个元素（索引0），终点指向最后一个元素（index numse nums.length -1）。

二进制搜索循环：
输入一个持续的循环，直到启动小于或等于结束。

计算中间索引：
计算中间索引中间为start +（end -start） /2。这确保了中间索引始终舍入整数，避免了潜在的溢出问题。< / p>

与目标相比：
检查索引中的元素是否等于目标值。
如果它们相等，请返回与找到目标的索引。

调整指针：
如果索引中的元素大于目标，则在当前范围的左半部分搜索更新到中间-1。

如果索引中的元素小于目标，则更新开始到中间 + 1，以在当前范围的右半搜索中搜索。

返回插入点：
如果段循环在没有找到目标的情况下退出（即，启动变得更大），则作为应插入目标的索引返回启动。

代码（在Java中）：

class Solution {
    public int searchInsert(int[] nums, int target) {
         int start = 0;
         int end = nums.length - 1;

         while(start <= end){
             int mid = start +(end - start) / 2;
             if(nums[mid] == target) return mid;
             if(nums[mid] > target) end = mid - 1;
             if(nums[mid] < target) start = mid + 1;
         }
         return start;
    }
}

时间复杂性分析：
二进制搜索具有O（log n）的时间复杂性，其中n是数组中元素的数量。这种方法可确保有效执行搜索。

愉快的编码，
湿婆