二分查找

二分查找是一种在有序数组中查找特定元素的高效算法。其基本思想是将待搜索区间分成两半，然后根据中间元素与目标值的比较结果来决定是继续在左半部分搜索还是右半部分搜索。二分查找的时间复杂度为 O(log n)，其中 n 是数组的长度。

二分查找的通用思路如下：

1. 确定搜索区间：开始时通常是整个数组。
2. 计算中间位置：取搜索区间的中间位置。
3. 比较中间元素与目标值：
   • 如果中间元素正好等于目标值，则查找成功。
   • 如果中间元素小于目标值，则目标值在中间元素的右侧，调整搜索区间为中间位置的右侧部分。
   • 如果中间元素大于目标值，则目标值在中间元素的左侧，调整搜索区间为中间位置的左侧部分。
4. 重复步骤 2 和 3，直到找到目标值或搜索区间为空。

下面是一个使用 Go 语言实现的二分查找算法的例子：

package main

import "fmt"

// 二分查找函数
func binarySearch(arr []int, target int) int {
    left, right := 0, len(arr)-1

    for left <= right {
        mid := left + (right-left)/2 // 防止溢出的写法
        if arr[mid] == target {
            return mid // 找到目标值，返回索引
        } else if arr[mid] < target {
            left = mid + 1 // 调整左边界
        } else {
            right = mid - 1 // 调整右边界
        }
    }

    return -1 // 没有找到目标值，返回-1
}

func main() {
    arr := []int{2, 3, 4, 10, 40}
    target := 10
    result := binarySearch(arr, target)
    if result != -1 {
        fmt.Printf("元素在数组中的索引为: %d\n", result)
    } else {
        fmt.Println("元素不在数组中")
    }
}

在实际应用中，二分查找算法可能需要根据具体问题进行适当的修改，例如处理查找第一个或最后一个等于目标值的元素，或者处理查找第一个大于等于或小于等于目标值的元素等情况。但基本的算法框架是相同的，都是通过不断缩小搜索区间来提高查找效率。