跳躍搜尋
跳躍搜尋是一種區間搜尋演算法。它是一種相對較新的演算法,只適用於排序陣列。它試圖比線性搜尋減少所需的比較次數,不像線性搜尋那樣掃描每一個元素。在跳躍搜尋中,陣列被分成 m 塊。它搜尋一個塊中的元素,如果該元素不存在,則移動到下一個塊。當演算法找到包含元素的塊時,它使用線性搜尋演算法來尋找精確的索引。這種演算法比線性搜尋快,但比二叉搜尋慢。 跳躍搜尋演算法 假設我們有一個未排序的陣列 A[],包含 n 個元素,我們想找到一個元素 X。 從第一個元素開始設定 i 為 0,塊大小 m 為√n。 當 A[min(m,n)-1]<X 且 i<n 時。 將 i 設為 m,並以√n 遞增 m。 If i >= n return -1。 當 A[i]< X 時,執行以下操作。 遞增 i 如果 i 等於 min(m,n) 返回 -1。 如果 A[i] == X,返回 i。 否則,返回 -1。 跳躍搜尋示例 假設我們有一個陣列:(1, 2, 3, 4, 5, 6, 7, 8, 9),我們想找到 X-7。