在O（logn）運行時間中通過數組？

Question

是否可以通過布爾數組來查找O（logn）運行時間中的假值？數組的索引從0運行到n-1。

如果是這樣，我們將如何在java中做到這一點？僞代碼很好。

Answer 1

不需要。如果沒有關於陣列的更多信息，這是不可能的。

您可以做的最好的是O(n)，它從左向右遍歷數組並檢查每個項目。

如果數組排序，則需要兩次檢查，兩端都會有一個錯誤值，即O(1)。

由矛盾的一個常見的證明：

假設算法工作正確。然後，在檢查少於所有元素之後，該算法產生正確的答案。現在假設算法只看到true s，它會得出答案x。現在只改變值的算法有而不是檢查，我總是可以構造一個算法失敗的測試用例。因此，該算法必須檢查（未排序）布爾數組的所有元素以確定是否全部爲真。

Answer 2

無論你做什麼，你都必須檢查所有的值，以確保沒有錯誤的價值。線性時間，平均n/2次檢查。

Answer 3

通常情況下，答案是「否」：除非您知道有關數組項目的順序，否則不能通過數組搜索小於O(N)的單個值。

例如，如果數組排序，您可以在O(log N)中找到正確的位置。

對於具有所有false S，如果有的話，在開始boolean陣列被排序裝置，以及所有true S，如果有的話，在結束。如果是這種情況，您可以使用二分查找找到對數時間的「分界點」。