二分搜索树

一、概念及其介绍

二分搜索树（英语：Binary Search Tree），也称为 二叉查找树 、二叉搜索树 、有序二叉树或排序二叉树。满足以下几个条件：

• 若它的左子树不为空，左子树上所有节点的值都小于它的根节点。
• 若它的右子树不为空，右子树上所有的节点的值都大于它的根节点。

它的左、右子树也都是二分搜索树。

如下图所示：

二、适用说明

二分搜索树有着高效的插入、删除、查询操作。

平均时间的时间复杂度为 O(log n)，最差情况为 O(n)。二分搜索树与堆不同，不一定是完全二叉树，底层不容易直接用数组表示故采用链表来实现二分搜索树。

下面先介绍数组形式的二分查找法作为思想的借鉴，后面继续介绍二分搜索树的查找方式。

三、二分查找法过程图示

二分查找法的思想在 1946 年提出，查找问题是计算机中非常重要的基础问题，对于有序数列，才能使用二分查找法。如果我们要查找一元素，先看数组中间的值V和所需查找数据的大小关系，分三种情况：

• 1、等于所要查找的数据，直接找到
• 2、若小于 V，在小于 V 部分分组继续查询
• 2、若大于 V，在大于 V 部分分组继续查询

详细解释：在有序列表中设置三个值左中右，将要对比的值和中间的值进行对比，等于则结束对比；大于则设置中间-1为最左边，截取出新的有序列表后，重新取中间值后进行对比；小于于则设置中间-1为最右边，截取出新的有序列表后，重新取中间值后进行对比。依次重复这个步骤直到等于中间值则查找到，不等于则说明没有查找到。

四、代码实例

PHP

function binarySearch($arr, $target) {
    $left = 0;
    $right = count($arr) - 1;

    while ($left <= $right) {
        $mid = floor(($left + $right) / 2);

        if ($arr[$mid] == $target) {
            return $mid; // 找到目标，返回索引
        }

        if ($arr[$mid] < $target) {
            $left = $mid + 1; // 目标在右侧，缩小搜索范围
        } else {
            $right = $mid - 1; // 目标在左侧，缩小搜索范围
        }
    }

    return -1; // 目标不存在，返回 -1
}

// 示例用法
$sortedArray = array(2, 5, 8, 12, 16, 23, 38, 56, 72, 91);
$targetValue = 23;

$result = binarySearch($sortedArray, $targetValue);

if ($result == -1) {
    echo "目标值不存在";
} else {
    echo "目标值的索引是： " . $result;
}

Python

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == target:
            return mid

        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

# 示例用法
sorted_array = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target_value = 23

result = binary_search(sorted_array, target_value)

if result == -1:
    print("目标值不存在")
else:
    print("目标值的索引是：", result)

Go

package main

import "fmt"

func binarySearch(arr []int, target int) int {
	left := 0
	right := len(arr) - 1

	for left <= right {
		mid := (left + right) / 2

		if arr[mid] == target {
			return mid
		}

		if arr[mid] < target {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}

	return -1
}

func main() {
	sortedArray := []int{2, 5, 8, 12, 16, 23, 38, 56, 72, 91}
	targetValue := 23

	result := binarySearch(sortedArray, targetValue)

	if result == -1 {
		fmt.Println("目标值不存在")
	} else {
		fmt.Println("目标值的索引是：", result)
	}
}