二進制 & |

Meta Binary Search is a one-sided binary search where we work on the index using bit manipulation. We are to find the target index by using bit manipulation like the below example where the algorithm is explained.

元二進制搜索是一種單面二進制搜索 ，我們在其中使用位操作來處理索引。 我們將通過使用位操作來找到目標索引，如下面的示例(其中解釋了該算法)。

Say the input array is [3, 4, 6, 8, 12, 14, 16] and searching key says 14.

假設輸入數組為[3、4、6、8、12、14、16] ，搜索鍵為14 。

The idea is to figure out the target index. And we will do that using bit manipulation and thus we will use the bit representation of the index. On each iteration, we will set the bits.

想法是找出目標索引。 并且我們將使用位操作來做到這一點，因此我們將使用索引的位表示形式。 在每次迭代中，我們將設置位。

Now the question is, how many bits can be there at maximum in the target index?

現在的問題是， 目標索引中最多可以有多少位？

Taking the worst case, it's the number of bits in the maximum index (array len-1). So for the above example, the maximum number of bits is 3 (max index 6 has 3 bits).

在最壞的情況下，它是最大索引(數組len-1 )中的位數。 因此，對于上面的示例，最大位數為3 (最大索引6為3位)。

Let's describe the bits as x₁x₂x₃

讓我們將位描述為x ₁ x ₂ x ₃

Now our work is to assign bits from left (MSB) to the right (LSB), 0, or 1 based on the values they should have. Now how would we assign 0 or 1, we will discuss now.

現在，我們的工作是根據應具有的值從左(MSB)到右(LSB)，0或1分配位。 現在我們將如何分配0或1，我們將進行討論。

First, we will try to put 1 always, if the current index found has value greater searching key then we will put 0, otherwise it's fine to put 1. If we find the current index found has the same value as the key then we are done.

首先，我們將嘗試始終放置1，如果找到的當前索引具有更大的搜索鍵值，則將放置0，否則將放置1。如果找到的當前索引具有與鍵相同的值，則我們將完成。

So let's start with the example,

讓我們從示例開始

The first bit to be set is the 0^th bit, MSB
First set it as 1

要設置的^第一位是第0位MSB
首先將其設置為1

So the current index is 1X₂X₃ where X₂X₃ is not either 0, not 1(not set at all). So the minimum current index is right now 100 which is 4(putting 0 in both X₂X₃ which will lead to minimum index). arr[4] is 12 and it's less than the searching key. Thus it's fine to put 1 at X1

因此，當前索引為1X ₂ X ₃ ，其中X ₂ X ₃既不是0，也不是1(根本沒有設置)。 因此，最小當前索引現在為100，即4(兩個X ₂ X ₃中都輸入0，這將導致最小索引)。 arr [4]為12，小于搜索關鍵字。 因此，在X1處放1很好

Now it's turn for the second bit.
Let's set it with 1 first

現在輪到第二位了。
首先設置1

So we have 11X₃, where X₃ is not either 0, not 1(not set at all). So the minimum possible current index is right now 110(6). arr[6] is 16 and it's greater than the searching key. Thus we can't set 1st bit as 1. So we need to set that as 0. X₂ =0
Now it's turn for the 2nd bit(LSB).

因此，我們有11X ₃ ，其中X ₃既不是0，也不是1(根本沒有設置)。 因此，最小可能的當前索引現在為110(6)。 arr [6]為16，并且大于搜索關鍵字。 因此，我們不能將第1位設置為1。因此，我們需要將其設置為0。X ₂ = 0
現在輪到第二個位(LSB)了。

Let's set it with 1 first

首先設置1

So we have 101, So the current index is right now 5(101). And, arr[5]=14. We found the searching key and it's at index 5.

所以我們有101，所以當前索引現在是5(101)。 并且，arr [5] = 14。 我們找到了搜索關鍵字，它位于索引5。

This is how Meta Binary Search works. The time complexity is the number of bits to represent the maximum index which is Log(n).

這就是元二進制搜索的工作方式。 時間復雜度是代表最大索引的位數Log(n)。

During the execution of the algorithm

在執行算法期間

We found that there can be two types of edge cases:

我們發現邊緣情況可能有兩種：

1. We may find any target index while executing which is more than the maximum possible index. Say for example the, length of array is 25. Then, the number of bits we need to represent the maximum index possible->5. So while processing we may need to process any index like 11111 which is more than the maximum index possible. Thus we need to keep a check for this kind of scenario.

   我們可能會在執行時發現任何目標索引，該目標索引大于最大可能索引。 假設數組的長度為25。然后，我們需要表示最大可能索引的位數-> 5。 因此，在處理時，我們可能需要處理比11111還要大的任何索引。 因此，我們需要檢查這種情況。

2. Secondly, the searching key may not even exist, in that case, out of the loop, we will return -1 indicating not found.

   其次，搜索鍵甚至可能不存在，在這種情況下，循環外，我們將返回-1表示未找到。

元二進制搜索算法在C ++中的實現 (Implementation of the meta binary search algorithm in C++)

#include <bits/stdc++.h>
using namespace std;
int logn(int n)
{
int count = 0;
while (n) {
count++;
n >>= 1;
}
return count;
}
int meta_binary_search(vector<int> arr, int key)
{
int n = arr.size();
int no_of_bits = logn(n - 1);
int cur_index = 0;
//iterating log(n) time
for (int shift = no_of_bits - 1; shift >= 0; shift--) {
//set current bit as 1
int new_cur_index = cur_index + 1 << shift;
if (new_cur_index >= n) {
//can't set bit as 1
}
else {
if (arr[new_cur_index] == key)
return new_cur_index;
//we can set bit as 1
else if (arr[new_cur_index] < key) { 
cur_index = new_cur_index;
}
}
}
//not found
return -1;
}
int main()
{
vector<int> arr{ 3, 4, 6, 8, 12, 14, 16 };
int key = 12;
//key found case
int index = meta_binary_search(arr, key);
if (index != -1)
cout << "key " << key << " found at: " << index << endl;
else
cout << "key " << key << " not found\n";
//key not found case
key = 9;
index = meta_binary_search(arr, key);
if (index != -1)
cout << "key " << key << " found at: " << index << endl;
else
cout << "key " << key << " not found\n";
return 0;
}

Output:

輸出：

key 12 found at: 4
key 9 not found

翻譯自: https://www.includehelp.com/algorithms/meta-binary-search-one-sided-binary-search.aspx

二進制 & |