【数组】leetcode35——搜索插入位置

编号35：搜索插入位置

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

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

示例 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.目标值所在的位置无非就是如下四种情况：

• 目标值在数组所有元素之前
• 目标值在数组的某两个数之间
• 目标值等于数组中的某个数
• 目标值在素组所有元素之后

2.由题目可知所给的数组为有序数组，且数组中无重复元素，则我们可以考虑使用二分法进行查找

二分查找涉及的很多的边界条件，逻辑比较简单，就是写不好。
例如到底是 while(left < right) 还是 while(left <= right)，到底是right = middle呢，还是要right = middle - 1呢？有时候就会搞混乱了??，但只要我们搞清楚就非常好写啦~

(ps:golang没有传统意义上的while循环语句，它遵循大道至简的原则，用一种语法表示其他多种语法，故golang中可以用for循环代替while循环)

对于[left,right]左闭右闭的情况 选择 while(left <= right) , right = middle -1
对于[left,right)左闭右开的情况，选择 while(left < right) , right = middle

即要在二分查找的过程中，保持不变量，这也就是「循环不变量」

代码如下：

/*采取左闭右闭情况*/
func searchInsert(nums []int, target int) int {
   left := 0
   right := len(nums) - 1
   for left <= right { //[left,right]  left==right有效
      //middle := (left + right) / 2
       middle := left + ((right - left) >> 1) //防止整数溢出相当于(left+right)/w 并利用移位提高速度 >>1 相当于除2
      if nums[middle] > target {
         right = middle - 1
      } else if nums[middle] < target 
         left = middle + 1
      } else { //此时target == num[middle]  返回索引
         return middle
      }
   }
   return right + 1 //返回插入的下标位置
}

【数组】leetcode35——搜索插入位置

原文：https://www.cnblogs.com/zmk-c/p/14364877.html