欣迪

出處: https://leetcode.com/problems/search-insert-position/

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.

You must write an algorithm with O(log n) runtime complexity.

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

Constraints:

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums contains distinct values sorted in ascending order.
  • -104 <= target <= 104

這次直接把思路寫在 code 上:

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
  	// 最左邊的位置
    let left = 0
    // 最右邊的位置
    let right = nums.length - 1
    // 中間的數字
    let idx = Math.ceil(right/2)
    // 如果比第一個數字小,直接放最前面
    if (target <= nums[left]) return 0
  	// 如果比最後一個數字大,直接方最後面
    if (target > nums[right]) return nums.length
  	// 開始循環,一直到縮小範圍到兩個位置之間
    while (right - left > 1) {
      	// 如果中間的數字大於要插入的數字,則範圍從右邊內縮
        if (nums[idx] >= target) {
            right = idx
        } else {
        // 如果中間數字小於要插入的數字,則範圍從左班內縮  
            left = idx
        }
      	// 調整中間的位置
        idx = left + Math.ceil((right - left) / 2)
    }
    return idx
};

訂閱 IT-Monk

訂閱最新文章的發布消息! 😚😚😚
Loading

作者介紹 - 欣迪

欣迪

從設計到寫程式,發現自己有追求前端技巧的自虐傾向。不斷的踩坑,再從坑裡爬出來,慢慢對攀岩有點心得。 目前在多間公司擔任網站設計顧問。 同時也是網站架設公司負責人。

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。