題目出處

447 · Search in a Big Sorted Array

難度

medium

個人範例程式碼 – Binary Search

class Solution:
    """
    @param reader: An instance of ArrayReader.
    @param target: An integer
    @return: An integer which is the first index of target.
    """
    def searchBigSortedArray(self, reader, target):
        start, end = 0, 1
        while(reader.get(end) <= target):
            end *= 2

        while(start + 1 < end):
            mid = (start + end) // 2
            if(reader.get(mid) == target):
                end = mid
            elif(reader.get(mid) < target):
                start = mid
            else: # (reader.get(mid) > target):
                end = mid
        else:
            if(reader.get(start) == target):
                return start
            elif(reader.get(end) == target):
                return end
            else:
                return -1

算法說明 – Binary Search

先不斷的 *=2 放大 end，直到找到一個比較可靠的右邊界為止

最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解

input handling

應該要做但我沒做XD，不過題目有保證輸入正確就是

Boundary conditions

binary search 的邊界條件

這裡有兩個 Boundary conditions 要注意，一個是一開始的 binary search 的邊界條件

個人範例程式碼 – Exponential backoff (倍增)

class Solution:
    """
    @param reader: An instance of ArrayReader.
    @param target: An integer
    @return: An integer which is the first index of target.
    """
    def searchBigSortedArray(self, reader, target):
        # write your code here
        first_element = reader.get(0)
        if first_element == target:
            return 0
        if first_element > target:
            return -1

        idx, jump = 0, 1
        while(jump):
            while(jump and reader.get(idx + jump) >= target): # bigger or same
                jump = jump // 2 # >> 1 # until 0
                print(jump)
            else: # when smaller
                idx += jump
                jump = jump * 2 # << 1 
        else:
            if reader.get(idx+1) == target:
                return idx+1
            else: # reader.get(start) > target:
                return -1

        return -1

算法說明 – Exponential backoff (倍增)

倍增法的概念，先不斷放大，當超過時再縮小範圍搜尋。

最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解

畫個示意圖吧!

input handling

應該要做但我沒做XD，不過題目有保證輸入正確就是

Boundary conditions

• 當 >= target 時，縮小 jump
• 當 < target 時，利用 idx + jump，並 jump 不斷的增加

Reference

• python 「>>， <<」 用法，BitwiseOperators
  • BitwiseOperators
• 在大数组中查找 · Search in a Big Sorted Array