完成顺序查找、折半查找以及二叉排序树上的查找算法，并比较相同数据量下的查找速度

1. 顺序查找算法

顺序查找算法，又称线性查找算法，是一种简单但效率较低的查找算法。其基本思想是从数据集合中第一个元素开始，逐个比较查找元素和数据集合中的元素是否相同，直到找到目标元素或者查找完整个数据集合为止。

代码实现如下：

def sequential_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

2. 折半查找算法

折半查找算法，也称二分查找算法，在有序数据集合中查找目标元素。其基本思想是首先找到有序数据集合的中间位置，然后将目标元素与中间位置的元素进行比较，如果相等则直接返回，否则根据目标元素与中间位置的大小关系，缩小查找范围，继续进行查找，直到找到目标元素或者查找范围为空为止。

代码实现如下：

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

3. 二叉排序树查找算法

二叉排序树（Binary Search Tree，简称BST）是一种基于二叉树的数据结构，它保证了每个节点都比其左子树中的节点大，比其右子树中的节点小。因此，可以利用二叉排序树进行查找操作。其基本思想是从根节点开始，根据目标元素与当前节点值的大小关系，不断向左子树或右子树查找，直到找到目标元素或者查找失败。

代码实现如下：

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

class BST:
    def __init__(self):
        self.root = None

    def insert(self, val):
        if not self.root:
            self.root = TreeNode(val)
        else:
            self._insert(self.root, val)

    def _insert(self, node, val):
        if node.val == val:
            return
        elif node.val < val:
            if not node.right:
                node.right = TreeNode(val)
            else:
                self._insert(node.right, val)
        else:
            if not node.left:
                node.left = TreeNode(val)
            else:
                self._insert(node.left, val)

    def search(self, val):
        return self._search(self.root, val)

    def _search(self, node, val):
        if not node:
            return -1
        if node.val == val:
            return node.val
        elif val < node.val:
            return self._search(node.left, val)
        else:
            return self._search(node.right, val)

4. 查找速度比较

我们通过比较同样大小的数据集合，在不同的查找算法下，所需的查找时间来比较它们的速度。

import time

def test_search_speed(arr, target):
    start_time = time.time()
    sequential_search(arr, target)
    end_time = time.time()
    print("Sequential Search Time: ", end_time - start_time)

    start_time = time.time()
    binary_search(arr, target)
    end_time = time.time()
    print("Binary Search Time: ", end_time - start_time)

    bst = BST()
    for i in arr:
        bst.insert(i)

    start_time = time.time()
    bst.search(target)
    end_time = time.time()
    print("BST Search Time: ", end_time - start_time)

arr = list(range(1000000))
target = 999999

test_search_speed(arr, target)

我们通过测试可以发现，二叉排序树查找的速度相对于其他两种算法是最快的，而顺序查找算法的速度最慢。这是因为顺序查找算法需要逐个比较每个元素，而折半查找算法和二叉排序树查找算法可以根据目标元素与当前元素的大小关系，缩小查找范围，减少比较次数，从而提高查找速度。