劍指Offer——在排序數組中查找數字I（JS實作）

題目描述

解題思路（序列化）

• 看到本題我首先想到的是二分查找
• 初始化左指針指向下标0，右指針指向下标nums.length - 1;
• 首先找到中位數下标，将中位數下标對應的值和target進行比較，如果比中位數大，right = mid - 1,如果比中位數小，left = mid + 1，如果中位數和target目标值相同則終止循環，并記錄目前的中位數下标
• 以中位數下标為flag，查找中位數左右兩邊和中位數相同的元素，并記錄下标
• 本題要求的就是下面的這個公式

右邊界−左邊界+1右邊界 - 左邊界 + 1右邊界−左邊界+1

• 注意有時候會有邊界溢出的情況，比如右指針到達負數

序列化代碼

var search = function (nums, target) {
    if (nums.length === 0) return 0;
    // 定義初始化指針
    let left = 0;
    let right = nums.length - 1;
    // 求中位數下标
    let mid = Math.floor((left + right) / 2);
    while (nums[mid] !== target) {
        if (left === right) return 0;
        if (nums[mid] < target) {
            left = mid + 1;
            if (left === nums.length) return 0;
            mid = Math.floor((left + right) / 2);
            continue;
        }
        if (nums[mid] > target) {
            right = mid - 1;
            if (right < 0) return 0;
            mid = Math.floor((left + right) / 2);
            continue;
        }
    }
    let flag = mid;
    let flag2 = mid;
    let left_border,right_border;
    while (nums[flag-1] === target) {
        flag--;
    }
    left_border = flag;
    while (nums[flag2+1] === target) {
        flag2++;
    }
    right_border = flag2;
    return right_border - left_border + 1;
};
      

總結（本題給我們的啟示思路）

• 啟示一：學會使用二分查找
• 啟示二：考慮邊界條件