LeetCode Js-35. Search Insert Position

    AllenLi
    LeetCode Js-Array

    Given a sorted array of distinct integers 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.

    提供一個由小到大的整數陣列和一個目標值，如果目標值存在陣列中，則回傳位置，反之回傳依排序下應放入之位置。

    Example 1:

    Input: nums = [1,3,5,6], target = 5
Output: 2

    Example 2:

    Input: nums = [1,3,5,6], target = 2
Output: 1

    Example 3:

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

    Solution:
    1. 先確認目標值是否存在陣列中，如「是」則回傳位置。
    2. 如「不是」則依序確認陣列中第一個比目標值大的數值，
    回傳它的位置。
    3. 如目標值不存在陣列，則放入陣列最後一個位置。

    Code 1:

    var searchInsert = function(nums, target) {
  //運用indexOf指令比對並回傳位置
  const targetIndex = nums.indexOf(target)
  if (targetIndex >= 0) return targetIndex //若不存在於陣列中，則indexOf()會回傳 -1。

  //使用for依序比對目標與陣列值得大小
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] > target) {
      return i
    }
  }
  //陣列沒有比目標值大，放到最後一個位置
  return nums.length
};

    FlowChart:
    Example 1

    step.1
targetIndex = nums.indexOf(target) //找到符合回傳位置
Array  =  0  1  2  3
nums   = [1, 3, 5, 6]
target =        5
return targetIndex //targetIndex = 2

    Example 2

    step.1
targetIndex = nums.indexOf(target) //targetIndex = -1 ，不存在陣列

step.2
Array  =  0  1  2  3
nums   = [1, 3, 5, 6]
target =     2   
Array[i] > target，return i //3 > 2，return 1

    Example 3

    step.1
targetIndex = nums.indexOf(target) //targetIndex = -1 ，不存在陣列

step.2
Array  =  0  1  2  3
nums   = [1, 3, 5, 6]
target =              7   
Array[i] < target，return i //陣列中沒有大於目標值的數
return nums.length //nums.length = 4，陣列的長度等於接下來陣列需新增的位置

    Remark.1: 暴力解 => 運用push()來將目標放入陣列中，在用sort()對陣列的數值進行排序，但要注意預設排序是根據Unicode的編碼位置。
    Code 2:

    var searchInsert = function(nums, target) {
  nums.push(target)
  nums.sort((a,b) => a - b)
  return nums.indexOf(target)
};

    Code 3: Binary Search

    var searchInsert = function(nums, target) {
  //宣告nums的左右位置
  let left = 0
  let right = nums.length - 1
  while (left <= right) {
    //宣告中間的位置為整數
    const middle = Math.floor(left + (right - left) / 2) //((left + right) / 2)
    //如果目標值位在陣列中間，回傳中間位置
    if (nums[middle] === target) {
      return middle
    //如果目標值比陣列中間值大，把右邊位置往左一格
    } else if (nums[middle] > target) {
      right = middle - 1
    //如果目標值比陣列中間值小，把左邊位置往右一格
    } else if (nums[middle] < target) {
      left = middle + 1
    }
  }
  //如果目標值不在陣列內，新增在陣列最後一個位置(nums.length)
  return right + 1
};

    Code 4: for loop desc

    var searchInsert = function(nums, target) {
  for (let i = nums.length - 1; i >= 0; i--) {
    if (target > nums[i]) return i + 1
    if (target === nums[i]) return i
  }
  return 0 
};

    left + (right - left) / 2 = (right + left / 2)

    (l+r)/2 =
l/2 + r/2 =
l/2 + r/2 + 0 =
l/2 + r/2 + (l/2 - l/2) =
(l/2 + l/2) + (r/2 - l/2) =
l + (r-l)/2

    source:https://cs.stackexchange.com/questions/80415/why-is-binary-search-using-this-weird-thing-to-calculate-middle

    Related Posts