Golang 实现二分查找算法

在编程中，为了从数组、链表或其他数据结构中搜索任何内容，我们有一些搜索算法，其中之一就是二分查找。在二分查找中，前提是数据应该是有序的。在二分查找中，我们采用分而治之的方法，通过应用一些条件将数据分割，并且仅对该数据执行操作。通过这种方式，我们减少了时间复杂度。

例如，如果我们有一个元素数组{20, 44, 45, 54, 67, 88, 91}，我们想要查找44，那么二分查找算法将以下列方式找到元素：

• 找到中间元素54并将其与要搜索的元素进行比较，即54大于我们将不会在右侧搜索，并且分割数组并向右移动。

• 现在数组为{20, 44, 45}，再次将其与中间元素进行比较，这次中间元素与我们要搜索的元素匹配。

步骤

步骤1： 通过使用import关键字在顶部导入所需的软件包。

步骤2： 然后主函数将首先运行。

• 首先，我们声明并初始化数组。

• 调用binarySearch()函数，通过参数传递数组、大小和要搜索的元素来搜索元素。

• 最后，打印结果，表示元素是否存在。

  步骤3.1： 在binarySearch()函数中

• 在第一个方法中，我们通过数组运行for循环，其中有两个迭代器left和right。

• 在循环内部，我们找到左边和右边的中间值，并将元素与索引m处的值进行比较。如果值匹配，则返回索引。

• 如果在索引m处的值大于我们要搜索的值，则将m-1赋值给迭代器right。

• 如果在索引m处的值小于我们要搜索的值，则将m赋值给迭代器left。

• 最后，如果元素不存在，则返回-1。

  步骤3.2： 在binarySearch()函数中

• 在第二种方法中，函数是递归的。

• 基本条件是，如果左迭代器大于等于右迭代器，则返回-1。

• 在递归函数内部，我们找到左右中间位置并将元素与索引m处的值进行比较。如果值匹配，则返回索引。

• 如果索引m处的值大于我们搜索的值，则通过将m-1传递给迭代器right调用binarySearch()函数。

• 如果索引m处的值小于我们搜索的值，则通过将m传递给迭代器left调用binarySearch()函数。

示例1

在这个示例中，我们将使用简单的for循环来实现二分搜索。在循环中，我们将找到索引right和left之间的中间元素。如果索引m处的元素与我们要搜索的元素匹配，则返回m并停止迭代，否则我们将相应地更新right和left，并继续迭代。

package main

import "fmt"

// function to print the array with array and
// size of the array as argument
func printArray(array []int, size int) {
    for i := 0; i < size; i++ {
        fmt.Print(array[i], " ")
    }
    fmt.Println()
}

// binary search function to find an element in the array
func binarySearch(array []int, size int, toFind int) int {
    var left, right, m int
    left = 0
    right = size

    for left < right {
        m = (right + left) / 2
        if array[m] == toFind {
            // if the element at index m is equal to the element we
            // are searching then returning m
            return m
        } else if array[m] > toFind {
            //If the element at index m is greater than the element
            //We are searching then we are skipping the right side
            // of the array
            right = m - 1
        } else {
            //If the element at index m is less than the element
            //We are searching then we are skipping the left side
            // of the array
            left = m
        }
    }

    return -1
}

func main() {
    // decalring and initializing the
    // array using the shorthand method
    array := []int{20, 44, 45, 54, 67, 88, 91}

    // decalring and initializing the
    // variable using the var keyword
    var toSearch int
    toSearch = 3

    fmt.Println("Golang program to find an element in an array using binary search using for loop.")
    fmt.Print("array: ")
    printArray(array, 6)
    // linear search function passing array and
    // variable as a parameter
    index := binarySearch(array, 6, toSearch)

    if index == -1 {
        fmt.Println(toSearch, "is not present in the array.")
    } else {
        fmt.Println(toSearch, "is present at index", index, "in the array.")
    }

}

输出

Golang program to find an element in an array using binary search recursively.
array: 20 44 45 54 67 88 
3 is not present in the array.

示例2

在这个示例中，我们将使用递归函数来实现二分查找。在递归调用中，我们将找到索引右侧和左侧之间的中间元素。如果索引m处的元素与我们正在搜索的元素匹配，则返回m并停止递归调用，否则根据情况更新右侧和左侧，并继续调用函数直到基本条件匹配为止。

package main

import "fmt"

   // function to print the array with array and
   // size of the array as argument
   func printArray(array []int, size int) {
      for i := 0; i < size; i++ {
         fmt.Print(array[i], " ")
      }
      fmt.Println()
   }

   // binary search function to find an element in the array
   func binarySearch(array []int, left int, right int, toFind int) int {
      if left >= right {
         // returning -1 if value not present in the array
         return -1
      }
      //Finding a middle index of the current array
      m := (right + left) / 2

     if array[m] == toFind {
        // if the element at index m is equal to the element we
        // are searching then returning m
        return m
     } else if array[m] > toFind {
        //If the element at index m is greater than the element
        //We are searching then we are skipping the right side
        // of the array
        return binarySearch(array, left, m, toFind)
     } else {
        //If the element at index m is less than the element
        //We are searching then we are skipping the left side
        // of the array
        return binarySearch(array, m+1, right, toFind)
    }
}

func main() {
    // decalring and initializing the
    // array using the short hand method
    array := []int{20, 44, 45, 54, 67, 88, 91}

    // decalring and initializing the
    // variable using the var keyword
    var toSearch int
    toSearch = 44

    fmt.Println("Golang program to find an element in an array using binary search recursively.")
    fmt.Print("array: ")
    printArray(array, 6)
    // linear search function passing array and
    // variable as a parameter
    index := binarySearch(array, 0, 6, toSearch)

    if index == -1 {
        fmt.Println(toSearch, "is not present in the array.")
    } else {
        fmt.Println(toSearch, "is present at index", index, "in the array.")
    }

}

输出

Golang program to find an element in an array using binary search using for loop.
array: 20 44 45 54 67 88 
44 is present at index 1 in the array.

结论

这是在Golang中进行二分查找的两种方法。第二种方法有多个函数调用，对于包含大量元素的数组，堆栈会超载。对于一个简单操作来说，这样做不是一个合适的编程方式，所以使用第一种通过for循环来运行的方法将更加高效。要了解更多关于Golang的知识，您可以探索这些 教程 。