#pragma once

/// <summary>
/// 顺序查找，O(n) = T(n)
/// </summary>
/// <typeparam name="TData">数组元素类型模板参数</typeparam>
/// <param name="list">数据容器（数组）</param>
/// <param name="size">容器（数组）长度</param>
/// <param name="data">待查找数据</param>
/// <returns>待查找数据在容器（数组）中的下标</returns>
template <typename TData>
int sequentialSearch(TData* list, int size, TData data)
{
	// 空列表处理
	if (size == 0)
		return -1;

	// 遍历查找
	int i = 0;
	while (i < size && list[i] != data)
	{
		i++;
	}

	// 返回结果
	if (i == size)
		return -1;
	return i;
}

/// <summary>
/// 二分查找，数组必须是升序排序好的，O(n) = T(logn)
/// </summary>
/// <typeparam name="TData">数组元素类型模板参数</typeparam>
/// <param name="list">数据容器（数组）</param>
/// <param name="size">容器（数组）长度</param>
/// <param name="data">待查找数据</param>
/// <returns>待查找数据在容器（数组）中的下标</returns>
template <typename TData>
int binarySearch(TData* list, int size, TData data)
{
	// 初始化左右边界
	int left = 0;
	int right = size - 1;

	// 查找
	while (left <= right)
	{
		int mid = (left + right) / 2;

		if (data > list[mid])
			left = mid + 1;
		else if (data < list[mid])
			right = mid - 1;
		else
			return mid;
	}

	// 没找到
	return -1;
}