排序算法
二分查找
用于有序元素列表的查找
性能：
| 时间复杂度 | 空间复杂度 |
|---|---|
| O (log n ) |
- Python实现：
def binary_search(list, item):
'''二分查找
list:数组列表
item：要查询的值
'''
num=0
low_index = 0
high_index = len(list)-1
while low_index <= high_index:
num+=1
mid = (low_index + high_index)//2
guess = list[mid]
if guess == item:
return "的索引为"+str(mid)+",查询次数为"+str(num)
if guess > item:
high_index = mid - 1
else:
low_index = mid + 1
return "值在数组中不存在,查询次数为"+str(num)
- C#实现
/// <summary>
/// 二分查找每个数
/// </summary>
/// <returns></returns>
public static string Binary_search(int[] list, int item)
{
var num = 0;
var low_index = 0;
var high_index = list.Length - 1;
while (low_index <= high_index)
{
num += 1;
var mid = (low_index + high_index)/2;
var guess = list[mid];
if (guess == item)
{
return $"的索引为{mid}查询次数为{num}";
}
else if (guess > item)
{
high_index = mid - 1;
}
else
{
low_index = mid + 1;
}
}
return $"值在数组中不存在,查询次数为{num}";
}
