javascript - 如果存在，如何在javascript中找到元素的索引？

Question

你能告诉我如何找到索引吗？我有个问题

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Example 1:

Input: [1,3,5,6], 5
Output: 2
Example 2:

Input: [1,3,5,6], 2
Output: 1
Example 3:

Input: [1,3,5,6], 7
Output: 4

我试过这样

var searchInsert = function(nums, target) {
          if (target > nums[nums.length - 1]) return nums.length;
    if (target < nums[0]) return 0;
    let start = 0,
        end = nums.length - 1,
        mid = Math.floor((start + end) / 2);
    while (start < end) {
        if(nums[mid] == target) return  mid
        if(nums[mid] > target) end = mid -1;
        if(nums[mid] < target) start = mid +1;
        mid = Math.floor((start + end) / 2);
    }
    return nums.length %2 == 0 ? mid +1 : mid
};

我的测试用例失败

Input
[1,3]
2
Output
2
Expected
1

我的测试用例仅在未找到要插入完美索引的元素时失败

更新的答案

var searchInsert = function (nums, target) {
    if (target > nums[nums.length - 1]) return nums.length;
    if (target === nums[nums.length - 1]) return nums.length-1;
    if (target < nums[0]) return 0;

    if (target ===nums[0]) return 0;
    let start = 0,
        end = nums.length - 1,
        mid = Math.floor((start + end) / 2);
    while (start <= end) {
        if(nums[mid] == target) return  mid
        if(nums[mid] > target) end = mid -1;
        if(nums[mid] < target) start = mid +1;
        mid = Math.floor((start + end) / 2);
    }
    return  nums[mid] > target ? mid : mid + 1;
};

感谢您的帮助，此代码在所有测试用例中都能完美运行

标签： javascriptdata-structures

Answer 1

问题在于你的最后一句话

return nums.length %2 == 0 ? mid +1 : mid

所以在最后一种情况下你的mid = 1as 因为数组的长度是你要添加的两个mid + 1

一种方法是从 while 本身返回值，以防在数组中找不到您的目标，条件是start === end

const searchInsert = function(nums, target) {
  if (target > nums[nums.length - 1]) return nums.length;
  if (target <= nums[0] || nums.length === 0) return 0;
  let start = 0,
    end = nums.length - 1,
    mid = Math.floor((start + end) / 2);
  while (start < end) {
    if (nums[mid] == target) return mid
    if (nums[mid] > target) end = mid - 1;
    if (nums[mid] < target) start = mid + 1;
    if(start >= end){
      return nums[mid] > target ? mid  : mid + 1 
    }
    mid = Math.floor((start + end) / 2);
  }
};

console.log(searchInsert( [1,3,5,6], 5)) // 2
console.log(searchInsert([1,3,5,6], 2)) // 1
console.log(searchInsert([1,3,5,6], 7)) // 4
console.log(searchInsert([1,3], 2)) // 1
console.log(searchInsert([1,2,3,5], 4)) // 3
console.log(searchInsert([1,2,3,4,5,7,9,10,15], 8)) //6
console.log(searchInsert([0, 1, 3, 4], 2)) // 2
console.log(searchInsert([1],1)) // 0
console.log(searchInsert([0],1)) // 1
console.log(searchInsert([],1)) // 0