二分查找法的输入是一个有序的元素列表, 如果要查找的元素包含在列表中, 二分查找返回其位置, 否则返回 null
Python 代码 (来源于《算法图解》一书):
- def binary_search(list, item):
- low = 0
- high = len(list)-1
- while low <= high:
- mid = (low + high)//2
- guess = list[mid]
- if guess == item:
- return mid
- if guess <item:
- low = mid + 1
- else:
- high = mid - 1
- return None
测试:
- >>>binary_search(my_list, 3)
- 1
- C# 代码 (因为我平时多用 C#):
- namespace Algorithms
- {
- public static class BinarySearch
- {
- public static int Binary_Search(List<double>list, double item)
- {
- int low = 0;
- int high = list.Count - 1;
- while(low <= high)
- {
- int mid = (low + high) / 2;
- double guess = list[mid];
- if (guess == item)
- return mid;
- else if (guess < item)
- low = mid + 1;
- else
- high = mid - 1;
- }
- return -1;
- }
- }
- }
大 O 表示法:
用于表示算法的速度有多快. O(n),n 表示最糟的情况下的操作数. 5 种经常遇到的大 O 运行时间.
O(log n) 对数时间, 比如二分法;
O(n) 线性时间, 比如简单查找;
O(n*log n) 包括快速排序法 (后面说);
O(n^2) 选择排序
O(n!) 旅行商问题的解决方案.
来源: http://www.bubuko.com/infodetail-3004305.html