知道排序數組中的最小值，如何使用二分查找？

Question

想象一下，您得到了一個已旋轉的排序數組，但您知道該數組中的最小值和索引。

如何在這個數組上編寫二進制搜索？

例如：

input array: [3,4,5,6,1,2] 
search value: 4 
min value index = 4 

謝謝！

Answer 1

這是可以做到一樣的，你會做二進制搜索排序的陣列上無旋轉，通過應用變換，當你看一個測試值的索引：

testIndex = (searchIndex + minIndex) % arrayLength; 

哪裏searchIndex是索引如果數組不旋轉，minIndex是數組旋轉的偏移量，而testIndex是用於從旋轉數組中查找值的索引。

所以在你的例子：

input array: [3,4,5,6,1,2] 
minIndex: 4 
first searchIndex: floor((arrayLength-1)/2) = 2 
first testIndex: (4+2)%6 = 0