c語言 二進制壓縮算法

by Pablo E. Cortez

由Pablo E.Cortez

使用C ++解釋的二進制搜索算法 (Binary Search Algorithms Explained using C++)

Binary search is one of those algorithms that you’ll come across on every (good) introductory computer science class. It’s an efficient algorithm for finding an item in an ordered list. For the sake of this example we’ll just assume this is an array.

二進制搜索是您在每門(入門)計算機科學入門課程中都會遇到的算法之一。 這是一種用于在有序列表中查找商品的高效算法。 為了這個例子，我們只假設這是一個數組。

The goals of binary search is to:

二進制搜索的目標是：

• be able to discard half of the array at every iteration
  每次迭代都能丟棄一半的數組
• minimize the number of elements we have to go through
  最小化我們必須經歷的元素數量
• leave us with one final value
  給我們一個最終的價值

Take for example the following array of integers:

以下面的整數數組為例：

int array[] = {     1, 3, 4, 6, 7, 8, 10, 13, 14, 18, 19, 21, 24, 37, 40, 45, 71 };

Let’s say we are trying to find the index value of the number 7 in this array. There are 17 items in total and the index values go from 0 to 16.

假設我們正在嘗試查找此數組中數字7的索引值。 共有17個項目，索引值從0到16。

We can see that the index value of 7 is 4, since it’s the fifth element in the array.

我們可以看到索引值為7，因為它是數組中的第五個元素。

But what would be the best way for the computer to find the index value of the number we are looking for?

但是，計算機找到我們要查找的數字的索引值的最佳方法是什么？

First, we store the min and max values, such as 0 and 16.

首先，我們存儲min和max ，例如0和16 。

int min = 0;int max = 16;

Now we have to come up with a guess. The smartest thing to do would be to guess an index value in the middle of the array.

現在我們不得不猜測。 最明智的做法是猜測數組中間的索引值。

With the index value 0 to 16 in this array, the middle index value of this array would be 8. That holds the number 14.

在此數組的索引值為0到16的情況下，該數組的中間索引值為8。該數字為14。

// This will round down if the quotient is not an integerint guess = (min + max) / 2;

// This will round down if the quotient is not an integer int guess = (min + max) / 2;

Our guess is now equal to 8, which is 14 in the array, since array[8] is equal to 14 .

我們的猜測現在等于8，在數組中為14，因為array[8]等于14 。

If the number we were looking for was 14, we would be done!

如果我們要查找的數字是14，那么我們將完成！

Since that is not the case, we will now discard half of the array. These are all the numbers after 14, or index value 8, since we know that 14 is greater than 7, and our guess is too high.

既然不是這種情況，我們現在將丟棄數組的一半。 這些都是14或索引值8之后的所有數字，因為我們知道14大于7，我們的猜測太高了。

After the first iteration, our search is now within: 1, 3, 4, 6, 7, 8, 10, 13

第一次迭代后，我們現在的搜索范圍是： 1, 3, 4, 6, 7, 8, 10, 13

We don’t have to guess in the last half of the original array, because we know that all those values are too big. That’s why it’s important that we apply binary search to an ordered list.

我們不必猜測原始數組的最后一半，因為我們知道所有這些值都太大。 這就是為什么將二進制搜索應用于有序列表很重要。

Since our original guess of 14 was greater than 7, we now decrease it by 1 and store that into max:

由于我們最初對14的猜測大于7，因此現在將其減少1，并將其存儲到max ：

max = guess - 1; // max is now equal to 7, which is 13 in the array

Now the search looks like this:

現在搜索如下所示：

1, 3, 4, 6, 7, 8, 10, 13

min = 0max = 7guess = 3

Because our guess was too low, we discard the bottom half of the array by increasing the min, conversely to what we previously did to max:

因為我們的猜測太低，所以我們通過增加min來丟棄數組的下半部分，這與之前對max所做的相反：

min = guess + 1; // min is now 4

By the next iteration, we are left with:

在下一次迭代中，我們剩下：

7, 8, 10, 13min = 4max = 7guess = 5

Since index value 5 returns 8, we are now one over our target. We repeat the process again, and we are left with:

由于索引值5返回8，因此我們現在比目標高1。 我們再次重復該過程，然后剩下：

7min = 4max = 4guess = 4

And we are left with only one value, 4, as the index of the target number we were looking for, which was 7.

我們只剩下一個值4，即我們要尋找的目標編號的索引，即7。

The purpose of binary search is to get rid of half of the array at every iteration. So we only work on those values on which it makes sense to keep guessing.

二進制搜索的目的是在每次迭代時擺脫數組的一半。 因此，我們只處理那些值得繼續猜測的值。

The pseudo-code for this algorithm would look something like this:

該算法的偽代碼如下所示：

1. Let min = 0 , and let max = n where n is the highest possible index value

   令min = 0 ，令max = n ，其中n是可能的最高索引值

2. Find the average of min and max , round down so it’s an integer. This is our guess

   找到min和max的平均值，將其四舍五入為整數。 這是我們的guess

3. If we guessed the number, stop, we got it!
   如果我們猜到了數字，停下來，我們知道了！

4. If guessis too low, set min equal to one more than guess

   如果guess值太低，則將min設置為比guess

5. If guessis too high, set max equal to one less than guess

   如果guess值太高，則將max設置為比guess小1

6. Go back to step two.
   回到第二步。

Here’s a solution, written in C++:

這是用C ++編寫的解決方案：

翻譯自: https://www.freecodecamp.org/news/what-is-binary-search-algorithm-c-d4b554418ac4/

c語言 二進制壓縮算法