iT邦幫忙

第 11 屆 iThome 鐵人賽

DAY 7
4
Software Development

從LeetCode學演算法系列 第 7

[Day 7] 從LeetCode學演算法 - 0035. Search Insert Position (Easy)

目標:
這題主要目的在於了解如何處理以排序陣列的快速方法:二元搜尋法。

原題:

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
Example 4:
Input: [1,3,5,6], 0
Output: 0

分析/解題:
給定一個排序的陣列和目標值,假定陣列的數字不會重複。
題目要求找到目標值在這個陣列中的位置;
若無,則回傳如果要將其插入時,應插入的位置。

這題是很典型的二元搜索法(Binary Search)
所謂的Binary Search,就是資料已處於被排序的狀態,
那麼在這些資料內搜索某個特定值就不用一個一個找,
我們可以用比較快的方法來搜尋。

假設我們有一組排序過的陣列,
搜尋的第一步就是取得中間點的那個值,我們先稱之為mid,
mid左邊的數必然小於mid,反之mid右邊的數必然大於mid
(按順序排的嘛XD)
所以我們拿目標值target跟mid比較,
如果target == mid,那mid所在的位置就是我們要的答案;
如果target > mid,表示答案只可能在mid右邊到尾端之間(不含mid)
如果target < mid,表示答案只可能在mid左邊到開頭之間(不含mid)
如此一來,每次取得區塊的中間點的值,並和target做比較,
每次都可以至少刪掉一半的可能的數量
直到找到答案(target == mid)
或是區塊上下限交錯(那就表示target不存在於陣列之中)
我們同樣可以將下限的index輸出,因為它就代表應該被插入的點。

例1. nums=[1,3,5,6], target=2
首先取下限lo = 0, 上限up = 3(頭跟尾), 中間點mi = (lo + up) / 2 = 1 ->
nums[1]為3, 3 > 2 -> 將up改為mi-1=0 -> mi = (0 + 0) / 2 = 0 ->
nums[0]為1, 1 < 2 -> 將lo改為mi+1=1 ->
lo和up已交叉,故結果應輸出1。

中間的值的變化如下:

lo  up  mi  nums[mi]
0   3   1   3
0   0   0   1
1   0   0   1

例2. nums=[1,3,5,6], target=5
首先取下限lo = 0, 上限up = 3(頭跟尾), 中間點mi = (lo + up) / 2 = 1 ->
nums[1]為3, 3 < 5 -> 將lo改為mi+1=2 ->mi = (2+3)/2 = 2 ->
nums[2]為5, 5==5 -> 直接輸出mi的值2即是答案。

中間的值的變化如下:

lo  up  mi  nums[mi]
0   3   1   3
2   3   2   5

下面也列出[1,3,5,6], 7跟[1,3,5,6], 0的值變化的過程,
有興趣或對整個邏輯還沒有弄得很明白的讀者可以嘗試推導一遍。

nums=[1,3,5,6], target=7 -> ans = 4

lo  up  mi  nums[mi]
0   3   1   3
2   3   2   5
3   3   3   6
4   3   3   6

nums=[1,3,5,6], target=0 -> ans = 0

lo  up  mi  nums[mi]
0   3   1   3
0   0   0   1
0   -1  -1  6        #(這個是用python輸出的,所以nums[-1] == 6)

底下的解法看個人喜好命名均可。

Java:

class Solution {
    public int searchInsert(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int i = 0, j = nums.length-1;
        int index = -1;
        while(i <= j) {            
            index = (i + j) / 2;  
            if(nums[index] == target)
                return index;
            if(nums[index] >= target)
                j = index - 1;
            else
                i = index + 1;          
        }
        return i;
    }
}

Python:

class Solution:
    def searchInsert(self, nums: 'List[int]', target: 'int') -> 'int':
        lo, up = 0, len(nums) - 1
        mi = (lo + up) // 2
        while lo <= up:
            if nums[mi] == target: 
                return mi
            elif nums[mi] > target:
                up = mi - 1
            else:
                lo = mi + 1            
            mi = (lo + up) // 2
        return lo

在這個解題過程,由於每次我們都會將範圍縮小一半,
所以總共比對的次數就相當於求這個陣列的長度是2的幾次方,
故時間複雜度為O(logN)
(電腦科學領域的對數一般不特別提的話通常是以2為底)

事實上,Java中也有提供 Arrays.binarySearch(int[] a, int key)
於utils的函式庫中,但有一點不一樣的是,當找不到target的時候,
如果插入該key所在位置為index,則回傳值為**-index-1**。
取負號是為了和key存在於陣列的狀況做分隔,
額外減1則是為了將key在0的位置key應該要插入在0的位置做區分。
(因為0取負號還是0)

Binary Search是在排序陣列或一些有序的資料結構中很常用到的演算法,
以後在談到**二元搜尋樹(BST, Binary Search Tree)**的時候也會用到它。
所以如何寫一個二元搜尋的簡單方法是很有用的,可以的話務請熟練XD

面試實際可能會遇到的問題:
「(Java)如果上限接近Integer.MAX_VALUE的話相加有overflow的可能?」
(將(lo+up)/2改成lo + (up-lo)/2,可以保證不會溢出)

「時間/空間複雜度?」
(O(logN), O(1))

「我想知道到底結果target是否存在array中,但不想額外加回傳的值?」
(如上面提到的,將插入的狀況改為**-index-1**來表達)

從LeetCode學演算法,我們下次見囉,掰~

下篇預告:
0053. Maximum Subarray (Easy)


上一篇
[Day 6] 從LeetCode學演算法 - 0026. Remove Duplicates from Sorted Array (Easy)
下一篇
[Day 8] 從LeetCode學演算法 - 0053. Maximum Subarray (Easy)
系列文
從LeetCode學演算法30

1 則留言

0
hyj1116
iT邦新手 4 級 ‧ 2019-10-03 23:27:36

感謝大大詳盡的解說,只是Java那邊找不到target時,回傳值為"-index-1"就有點不太懂為何是-1,不能是-2或-3或其他數值嗎?

然後文章中這段文字 "2 -> mi = (0 + 2) / 2 = 1 -> nums[1]為3, 3 > 2 -> 將up改為mi-1=" 多打了;還有這段文字 "將lo改為mi+1=2 ->mi = (2+3)/2 = 1 ->nums[2]為5, 5==5?" 裡面的mi應該是2。

Desolve iT邦新手 5 級 ‧ 2019-10-04 00:51:29 檢舉

當binary search有搜尋到陣列中的値,
我們會回傳其index,當未搜尋到的時候,
要回傳應該插入的index。
直覺要做區分的話就是加上負號是最快的。
但如果結果是0得話,由於加上負號以後還是0,
就無法區分你究竟是找到這個值或沒有找到XD。

而軟體工程原則上會盡量降低表示的成本,
用-index-1時,當你發現結果回傳負數(假設我們叫它x),
你可以用-x-1來得到實際上應該插入的index,
它們剛好是對稱的操作,
所以Java所使用的這種回傳方式是很漂亮的。
固然規定好的話,也可以-2或-3甚至其他數值,
但顯然使用-1會是不錯的選擇。

後面兩點的確筆誤了XD
感謝你的提醒更正,我會再做修改: )。

hyj1116 iT邦新手 4 級 ‧ 2019-10-04 23:27:52 檢舉

/images/emoticon/emoticon41.gif 話說-index-1剛好等於index的2補數。

Desolve iT邦新手 5 級 ‧ 2019-10-07 08:39:45 檢舉

原來如此XD! 那我想你找到了一個更合理的解釋了!
感謝分享~

我要留言

立即登入留言