如何查找排序數組中索引的偏移量

請考慮我有一個有0到N-1偏移量的排序數組的數組，其中N是數組的長度。一個完全排序後的數組具有如下面給出如何查找排序數組中索引的偏移量

[1, 2, 4, 11, 15, 19, 26]

陣列[19, 26, 1, 2, 4, 11, 15]具有2的偏移量爲較小的數字從第二索引和纏繞到第一開始0零偏移。

賦值問題是如何找到數組中一個數字的索引。對於排序數組，解決方案顯然是一個二分查找來查找索引（有或沒有遞歸）。

你如何找到一個數組的索引與偏移？偏移量未知。我想爲解決方案提供一個大綱，並且我會嘗試以我熟悉的語言實現它。

2013-08-18 Kartik

我不知道你在問什麼。對於具有零偏移量的微不足道的情況，「x」的索引是「x-1」 - 不需要二分搜索。對於數組有偏移量的一般情況，偏移量顯然是'1 - array [0] + N'。所以再次用模操作很容易找到任何數字的索引。我錯過了什麼嗎？ – Jon

@Jon - 示例數組是一種簡化。數字不一定是按升序或降序排列，它們之間有固定的數字差異。他們可以以任何順序。 – Kartik

@Kartik：好的，現在有道理。 – Jon

使用三元搜索找到數組的最大元素。所以我們假設X是數組最大元素的索引。所以如果X < N-1，偏移量將是X + 1，否則偏移量= 0。

然後，您可以對eash元素進行兩次二元搜索以查找該數字的索引。第一個將在0 - (offset-1)範圍內運行，第二個將在offset - N之間運行。如果你被允許使用更多的空間，那麼你也可以追加數組到自己，然後爲每個查詢做一個單一的二進制搜索offset - (N+offset-1)

2013-08-18 19:34:53 Fallen

回答