题目地址

解题思路

根据题目要求，要在一个已经排序好的数组中搜索目标元素，如果元素存在，返回对应的下标值，如果不存在，将目标数据插入数组中，并返回对应的下标。要求复杂度为O(logn)，所以可以想到用二分查找来处理，这里的难点主要是如何判断停止的条件。

代码

  1. var searchInsert = function(nums, target) {
  2.  const len = nums.length;
  3.  let left = 0,right = len -1,ans = len ;
  5.  while(left <=right){
  6.    let mid = Math.floor((right-left)/2) + left ; // 右移相当于Math.floor((right-left)/2)
  7.    // 中间值小于等于目标值，那么目标值的数组范围应该是右侧的
  8.    if (target <= nums[mid]) {
  9.         ans = mid;
  10.         right = mid - 1;
  11.     } else {
  12.         left = mid + 1;
  13.     }
  15. };
  16. return ans;
  17. }
  19. const nums = [1,3,5,6], target = 2;

总结

  • 在没看题解前，我是用的递归的形式，然后在处理递归终止的条件时，返回结果老是有问题，因而这块需要再多梳理一下。注意：这里处理话的ans = len，全部不满足时，要插入的位置就是整个数组的长度
  • 此外，在题解中，有一个写法：
  1. ((right - left) >> 1)

这个等价于

  1. Math.floor((right-left)/2)

主要是应用了位运算符

拓展

排序算法集锦