LeetCode 第35題 Search Insert Position－讀樂島

問題：
給一已排序的數字陣列和一目標數字，回傳目標數字的位置。如目標數字不在陣列裡，回傳適合插入該數字的位置。使用時間複雜度為O(log n)的演算法。

範例：
1. 輸入：nums = [ 1, 3, 5, 6 ], target = 5
輸出： 2
2. 輸入： nums = [ 1, 3, 5, 6 ], target = 2
輸出： 1
3. 輸入： nums = [ 1, 3, 5, 6 ], target = 7
輸出： 4

提問：
沒有

一般想法：
線性搜尋，但這是O(n)。

進階解法：
二元搜尋

程式：

+var searchInsert = function (nums, target) {
+    let lo = 0;
+    let hi = nums.length - 1;
+    while (lo <= hi) {
+        let mi = Math.floor((lo + hi) / 2);
+        if (target > nums[mi]) {
+            lo = mi + 1;
+        } else if (target < nums[mi]) {
+            hi = mi - 1
+        }
+        else {
+            return mi;
+        }
+    }
+    return lo;
+};

讀樂島主

讀樂島

讀樂島主發表在痞客邦留言(0) 人氣()

E-mail轉寄

讀樂島