大家好，如果您熟悉一些数据结构，那么现在该学习一些算法了。最基本但非常重要的主题，即二进制搜索。

我可以在不知道算法的情况下进行编码，为什么我会不愿意去学习它们呢？

当然，您可以在不技术上使用算法的情况下构建软件，这不是强制性的（我想是这样）。但是，当您解决软件问题时，您是否曾经问过自己“我能做得更好吗？”。这就是算法发挥作用的地方，最终，这种思想使您成为更好的程序员。

让我解释一下为什么它很重要。

像Facebook这样的服务拥有超过27亿用户，这意味着Facebook工程师大概必须处理大量用户的数据。有程序A和程序B处理这些数据。程序A需要1秒钟来处理每个用户的数据，而对方则需要2秒。这两个程序之间的速度差是多少？好吧，您甚至不需要计算它们，B花费的时间是A的两倍。

算法是关于如何有效地解决问题，您需要像计算机那样思考。
最广泛使用的算法是搜索和排序，今天我将讨论搜索算法。

线性搜寻

我们不能不了解线性搜索就跳入二进制搜索。您必须熟悉此算法，这是一种使用从0到数组末尾的for循环在数组中查找元素的方法。它需要n次，因为它将在这种情况下从0到5每次循环检查目标是否在索引中。线性搜索的时间复杂度为O（n）

看起来还不错，但是我们可以做得更好吗？
是的，我们可以通过使用二进制搜索使其更好。

二元搜寻

它的工作方式类似于线性搜索，但不同之处在于，它将减少一半的数组，从而减少了搜索范围，这意味着可以节省搜索时间，直到找到目标为止。

让我们在现实生活中看一下该算法。

您有一本字典来找到一个单词，您正在寻找单词“光荣”。首先，您从中间打开字典，现在在此M部分。其次，由于该G部分位于本书的前端，因此无需超越该M部分。第三，因此，您在开头和M小节之间再次随机打开，现在处于F小节中，这意味着您将不得不在F小节和M小节之间查找，直到找到该G小节。你明白了。

因此，基本上它可以缩小搜索范围，直到找到目标为止。

现在让我们更深入。我们43将从这个数组中找到数字[14, 3, 28, 64, 43, 90]。等等，我们不能真正使用二进制搜索，因为它的顺序不正确，无法确定搜索范围！是的…只有在对数组排序后，我们才可以进行二进制搜索。让我们先对其进行排序。

第1步。所以，和和在这种情况下。

left = 0right = arr.lengthmid = (left + right) / 2

让我们检查一下我们当前的中点是否为目标。是28 == 43真的吗没有！好吧，我们现在该怎么办？因为28小于43，我们将left指针移到中点的右侧。

步骤2. 由于我们向左移动了指针，所以指针将再次位于左右中间，即现在。让我们再次检查是否找到43。是真的吗？没有！然后大于或小于？大于。然后我们需要将右指针移到中点的左侧。

mid(3 + 5) / 2 = 4 ((left+right) / 2)64(middle) == 43(target)64436443

步骤3. 现在，中点在索引[3]处。所以中点是。但是，如果左+右是一个多么奇怪的数字，是不是可分？例如，如果left + right是，然后将它们除以得到us ，这不是可用于索引的整数。如果您来自python背景，则将需要使用整数除法器（如），该除法器将删除小数点然后返回3。是吗？是的！让我们返回中间指针3。

left + right = 66 / 2 = 3723.5left + right // 243(middle) == 43(target)

您采取了多少步骤才能找到43？

我们花了3步，如果n是数组的长度，我们大约花了n / 2步，这比线性搜索要短得多，并且相对于N的大小，它会变得更小，如果N的大小很大。因此，我们完成了n次工作的一半，可以表示为1/2 * 1/2 * 1/2 * 1/2 * 1/2 = log5（假设对数为2）。因此，时间复杂度为O（log2N）

实作

二进制搜索有两种实现方式，即迭代和递归。为了简单起见，我将给出一个迭代的实现示例。在类似python的伪代码中：

def binary_search(arr, target):
  left = 0
  right = arr.length - 1
  while left <= right:
    mid = (left + right) // 2
    # When found target
    if arr[mid] == target:
      return mid
    # When target is less than midpoint value
    elif target < arr[mid]:
      right = mid - 1  # move right pointer to left of mid
    # When target is greater than midpoint value
    else:
      left = mid + 1  # move left pointer to right of mid
  return -1