在Python中实现的搜索算法实现

实现搜索总是具有挑战性但并非不可能。

在现实生活中，我们会无规律地搜索。我们只会去我们认为可能放置的地方。在大多数情况下，我们不遵循任何规律。

在编程世界中是否也是如此呢？

不！在程序中搜索东西必须要有一些规律。本文中我们将会看到一些遵循不同模式的搜索算法。

在编程世界中有很多种算法。本文中我们将讨论最重要且最常用的算法。其他算法对你来说将会很容易学习。

本文中搜索是指在数组中搜索一个元素。

让我们逐个来看。

线性搜索

这个名字暗示了线性搜索算法遵循线性模式来搜索数组中的元素。该算法从数组的开头开始搜索元素，直到找到为止。当找到所需元素时，程序的执行将停止。

让我们通过一些酷炫的插图来说明线性搜索算法，以便更好地理解该算法。

如果你仔细观察搜索模式，你会发现程序执行所需的时间会在最坏的情况下花费O(n)。我们必须考虑算法的最坏情况时间复杂度进行分析。因此，该算法的时间复杂度为O(n)。

让我们看一下线性搜索算法的实现。

线性搜索实现

现在，你已经对线性搜索算法有了很好的理解。是时候动手写一些代码了。让我们首先看一下实现线性搜索的步骤。然后你可以尝试一下。如果你无法完成，不用担心，之后我会提供代码给你。

让我们看一下实现线性搜索算法的步骤。

• 初始化一个元素数组（你的幸运数字）。
• 编写一个名为search_element的函数，该函数接受三个参数，数组、数组的长度和要搜索的元素。
• search_element(arr, n, element)：
  • 遍历给定的数组。
    • 检查当前元素是否等于所需元素。
    • 如果是，则返回True。
  • 循环结束后，如果执行仍然在函数中，则表示元素不在数组中。因此返回False。
  • 根据函数search_element的返回值打印消息。

  最后，根据上述步骤编写代码来实现线性搜索算法。

  你完成了线性搜索算法的实现吗？希望如此。如果你完成了，请与下面的代码进行核对。

  如果你没有完成，不用担心，看一下下面的代码，学习我们是如何实现的。你将毫不费力地理解。

  ## 搜索函数
  def search_element(arr, n, element):

  ## 遍历数组
  for i in range(n):

  ## 检查当前元素是否与要查找的元素匹配
  if arr[i] == element:
  ## 匹配成功，返回True
  return True

  ## 如果元素未找到，则执行到这里
  return False

  if __name__ == ‘__main__':
  ## 初始化数组、长度和要查找的元素
  arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] n = 10
  element_to_be_searched = 6
  # element_to_be_searched = 11

  if search_element(arr, n, element_to_be_searched):
  print(element_to_be_searched, “找到了”)
  else:
  print(element_to_be_searched, “未找到”)
  

  首先，使用数组中存在的元素执行程序。然后，使用数组中不存在的元素执行程序。

  线性搜索算法的时间复杂度为O(n)。

  我们能否通过不同的方法进一步减少时间复杂度呢？

  是的，我们可以。让我们看看。

  二分搜索

  二分搜索算法总是检查数组的中间元素。该算法在有序数组中搜索元素。

  二分搜索算法遍历数组，并检查中间元素，如果找到，则停止程序。如果中间元素小于要查找的元素，则从中间元素开始省略数组的左侧部分进行搜索。如果中间元素大于要查找的元素，则从中间元素开始省略数组的右侧部分进行搜索。

  在每次迭代中，二分搜索算法都会减少搜索元素的区域。因此，检查的次数少于线性搜索算法中的检查次数。

  插图有助于更好地理解二分搜索算法。让我们来看看。

  

  二分搜索算法的时间复杂度为O(log n)。在每次迭代中，搜索区域的长度减半。它以指数方式减少。

  二分搜索实现

  首先，我们将看到实现二分搜索算法的步骤，然后是代码。让我们看看完成二分搜索算法实现的步骤。

  • 用元素初始化数组（你的幸运数字）
  • 编写一个名为search_element 的函数，该函数接受三个参数：排序数组、数组长度和要搜索的元素。
  • search_element(sorted_arr, n, element):
    • 为数组迭代初始化索引变量i。
    • 接下来，初始化两个变量，用于维护数组的搜索区域。在这里，我们称它们为开始和结束，因为它们指示索引。
    • 迭代，直到 i 小于数组的长度。
      • 使用开始和结束值计算搜索区域的中间索引。即（开始+结束）// 2 。
      • 检查搜索区域中的中间索引元素是否等于所需元素。
      • 如果是，则返回True。
      • 否则，如果中间索引元素小于要查找的元素，则将搜索区域的开始索引移动到中间+1。
      • 否则，如果中间索引元素大于要查找的元素，则将搜索区域的结束索引移动到中间-1。
      • 增加数组的索引i。
    • 循环结束后，如果执行仍在函数中，则元素不在数组中。因此返回False。
    • 根据函数search_element的返回值打印消息。

    尝试编写与线性搜索算法实现类似的代码。

    …

    你得到代码了吗？

    是的，将其与下面的代码进行比较。不，不要担心；通过下面的代码来理解实现。

    ## searching function
    def search_element(sorted_arr, n, element):
    
    	## array index for iteration
    	i = 0
    
    	## variables to track the search area
    	## initializing them with start and end indexes
    	start = 0
    	end = n - 1
    
    	## iterating over the array
    	while i < n:
    		## getting the index of the middle element
    		middle = (start + end) // 2
    
    		## checking the middle element with required element
    		if sorted_arr[middle] == element:
    			## returning True since the element is in the array
    			return True
    		elif sorted_arr[middle] < element:
    			## moving the start index of the search area to right
    			start = middle + 1
    		else:
    			## moving the end index of the search area to left
    			end = middle - 1
    		i += 1
    	return False
    
    
    if __name__ == '__main__':
    	## initializing the array, length, and element to be searched
    	arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    	n = 10
    	element_to_be_searched = 9
    	# element_to_be_searched = 11
    
    	if search_element(arr, n, element_to_be_searched):
    		print(element_to_be_searched, "is found")
    	else:
    		print(element_to_be_searched, "is not found")
    

    使用存在和不存在的不同情况对代码进行测试。

    结论

    二分搜索算法比线性搜索算法更高效。对于二分搜索算法来说，我们需要对数组进行排序，而线性搜索算法则不需要。排序需要一些时间。但是，使用高效的排序算法与二分搜索算法结合使用会形成一个很好的组合。

    现在，你对最广泛使用的算法有了很好的了解。

    接下来，请了解一些流行的。

    编码愉快 🙂 🧑‍💻

    相关