二分搜尋法
含有「二分搜尋法」共 4 篇內容
全部內容
發佈日期由新至舊
題目敘述 Find K-th Smallest Pair Distance
給定一個輸入陣列nums和 參數k。
請找出第k小的pair distance是多少?
pair distance定義為 abs( nums[i] - nums[j]), i 不等於j
也就是任意兩陣列元素差值的絕對值
給定一個輸入非負整樹陣列nums，請找出k值，使得陣列中恰好有k個元素大於等於 k。如果無解，回傳-1。尋找k值的方法包括排序法和二分搜尋法，時間複雜度都為O(n log n)，空間複雜度為O(1)。關鍵知識點是當解空間具有遞增或遞減的性質時，可以用二分搜尋法加快搜尋效率。
我來坐坐🤗
這篇文章，會帶著大家複習以前學過的二分搜尋法(Binary Search)框架，
並且以二分搜尋法的概念為核心，
貫穿一些相關聯的題目，透過框架複現來幫助讀者理解這個實用的演算法框架。
Binary search 二分搜尋法框架
用途:
在已經排序好的數列中尋找目標值。
題目給定一個已排序的輸入陣列，陣列裡面的數字自分別代表每篇論文的被引用數。
要求我們計算h-index。
h-index的定義:
找一個最大的h值，使得有h篇論文，個別論文的被引用數都 大於等於 h
