二進制搜索，獲得原始索引數組中的

我有一個數組「一」這樣的：二進制搜索，獲得原始索引數組中的

let a = [1.0, 2.0, 10.0, 0.0, 5.0] // original array

我期待找到「一個」使用二進制搜索次數10.0。

對於我的數組排序，得到數組「ASR」：

let asr = a.sorted() 
print(asr) 
// [0.0, 1.0, 2.0, 5.0, 10.0]

在「ASR」 10.0將返回我的指數= 4。然而，我作爲尋找指數= 2的二進制搜索原始數組「a」。而且我也在尋找速度，因爲我的陣列很長。

有什麼建議嗎？

我貼我使用二進制搜索算法如下：

func binarySearch<T:Comparable>(inputArr:Array<T>, searchItem: T)->Int{ 
var lowerIndex = 0; 
var upperIndex = inputArr.count - 1 

while (true) { 
    let currentIndex = (lowerIndex + upperIndex)/2 
    if(inputArr[currentIndex] == searchItem) { 
     return currentIndex 
    } else if (lowerIndex > upperIndex) { 
     return -1 
    } else { 
     if (inputArr[currentIndex] > searchItem) { 
      upperIndex = currentIndex - 1 
     } else { 
      lowerIndex = currentIndex + 1 
     } 
    } 
    } 
}

我給比如我X（時間）和Y（值）陣列。對於多個這樣的數組，我需要在y中找到最大值並存儲相關的唯一x值。

let x = [230.0, 231.0, 232.0, 233.0, 234.0, 235.0, 236.0, 237.0, 238.0, 239.0, 240.0, 241.0, 242.0, 243.0, 244.0, 245.0, 246.0, 247.0, 248.0, 249.0, 250.0, 251.0, 252.0, 253.0, 254.0, 255.0, 256.0, 257.0, 258.0, 259.0, 260.0, 261.0, 262.0, 263.0, 264.0, 265.0, 266.0, 267.0, 268.0, 269.0, 270.0, 271.0, 272.0, 273.0, 274.0, 275.0, 276.0, 277.0, 278.0, 279.0, 280.0, 281.0, 282.0, 283.0, 284.0, 285.0, 286.0, 287.0, 288.0, 289.0, 290.0, 291.0, 292.0, 293.0, 294.0, 295.0, 296.0, 297.0, 298.0, 299.0, 300.0, 301.0, 302.0, 303.0, 304.0, 305.0, 306.0, 307.0, 308.0, 309.0, 310.0, 311.0, 312.0, 313.0, 314.0, 315.0, 316.0, 317.0, 318.0, 319.0, 320.0, 321.0, 322.0, 323.0, 324.0, 325.0, 326.0, 327.0, 328.0, 329.0, 330.0, 331.0, 332.0, 333.0, 334.0, 335.0, 336.0, 337.0, 338.0, 339.0, 340.0, 341.0, 342.0, 343.0, 344.0] // unique ascending time stamps 

let y = [-0.0050202642876176198, 0.022393410398194001, 0.049790254951834603, 0.077149678828730195, 0.104451119608423, 0.131674058448602, 0.15879803550636501, 0.185802665315146, 0.21266765210574901, 0.239372805059962, 0.26589805348529699, 0.29222346189943499, 0.31832924501308402, 0.34419578259991401, 0.36980363424246498, 0.39513355394291599, 0.42016650458771598, 0.444883672255248, 0.46926648035572899, 0.49329660359275201, 0.51695598173596602, 0.54022683319452802, 0.56309166838114799, 0.58553330285668204, 0.60753487024536401, 0.62907983491101405, 0.65015200438466503, 0.67073554153427395, 0.690814976467372, 0.71037521815772098, 0.72940156578721904, 0.74787971979453605, 0.765795792622184, 0.783136319153938, 0.79988826683476, 0.816039045465632, 0.83157651666592303, 0.84648900299618601, 0.86076529673452795, 0.87439466829995904, 0.88736687431637595, 0.89967216531114802, 0.91130129304248497, 0.92224551745010597, 0.93249661322397404, 0.94204687598616199, 0.95088912808120296, 0.95901672397057403, 0.96642355522725798, 0.97310405512663301, 0.979053202830236, 0.98426652715924901, 0.98874010995489703, 0.99247058902319396, 0.99545516066186102, 0.99769158176748995, 0.99917817152138799, 0.99991381265282298, 0.99989795227872502, 0.99913060231921702, 0.99761233948865402, 0.99534430486218395, 0.99232820301815805, 0.98856630075702201, 0.98406142539766805, 0.97881696265251605, 0.97283685408292797, 0.96612559413686105, 0.95868822677099297, 0.95053034165985795, 0.94165806999482904, 0.93207807987612601, 0.92179757130129403, 0.91082427075393002, 0.89916642539671898, 0.88683279687313799, 0.87383265472251104, 0.86017576941332496, 0.84587240500008198, 0.83093331140918203, 0.81536971635963695, 0.79919331692469797, 0.78241627074072795, 0.76505118686993401, 0.74711111632382299, 0.72860954225449404, 0.70956036982116599, 0.68997791573951905, 0.66987689752174295, 0.649272422415344, 0.62817997604904996, 0.60661541079433601, 0.584594933851312, 0.56213509506794002, 0.53925277450172504, 0.51596516973324402, 0.49228978294099801, 0.46824440774739501, 0.44384711584564701, 0.41911624341769299, 0.39407037735334999, 0.36872834128103499, 0.34310918142055002, 0.31723215226859403, 0.291116702127733, 0.26478245848970899, 0.23824921328407, 0.21153690800324301, 0.18466561871516801, 0.157655540974798, 0.130526974645817, 0.10330030864392201, 0.07599600561323, 0.048634586547227202, 0.0212366153658834] // y values (could be repeating)

來源

2017-02-07 Pat

很好排序數組的時間複雜度爲O（nlog（n）），所以你已經更好地做線性搜索了。 – Hamish

如果您在* large *數組上執行* multiple *搜索，那麼您可以使用'a.enumerated（）。sorted（by：{$ 0.element <$ 1.element}）'創建一個索引/元素對的排序數組，然後對其進行二分法搜索以找到與原始索引一起的元素。 –

使用另一個保存索引的數組。像：

let indexArray = [0, 1, 2, 3, 4]

然後，只要您切換原始數組中的數字，切換indexArray中的等效值。

在年底的指數陣列是這樣的：

[3, 0, 1, 4, 2]

使用這個，你可以很容易地得到原始指標。如果您發送您使用的排序我可以改變的代碼，並告訴你如何做到這一點的代碼..

另一種方法：

您可以保留原來的數組的一個副本：

let copyArray = a.copy()

，然後用它來找到每個值的索引：

let indexOfA = copyArray.index(of: "aValue") 
copyArray[indexOfA] = nil 
// OR if the values are all positive 
copyArray[indexOfA] = -1

來源

2017-02-07 14:42:38 Besat

謝謝貝薩！我編輯了我的帖子以包含二進制搜索代碼。 – Pat

不用擔心。你需要在排序數組的時候這樣做，所以我需要你排序的代碼部分，而不是你在排序數組中搜索的部分 – Besat

我只是使用「let asr = a.sorted（）」 – Pat

是很自然的表達二進制搜索的遞歸算法 - 通常更清楚，至少當y你對遞歸感到滿意。這個怎麼樣：

func binarySearchHelper <T:Comparable> (array: Array<T>, item:T, lower:Int, upper:Int) -> Int? { 
    guard lower <= upper else { return nil } 

    let center = (lower + upper)/2 

    return array[center] == item 
    ? center 
    : ((lower == center  ? nil : binarySearchHelper (array: array, item: item, lower: lower,  upper: center)) ?? 
     (upper == center + 1 ? nil : binarySearchHelper (array: array, item: item, lower: center + 1, upper: upper))) 
} 

func binarySearch <T:Comparable> (array: Array<T>, item:T) -> Int? { 
    return binarySearchHelper (array: array, item: item, lower: array.startIndex, upper: array.endIndex) 
}

來源

2017-02-07 15:28:36 GoZoner

二進制搜索，獲得原始索引數組中的

回答

相關問題