简单查找算法

最近感觉自己需要一点算法知识，所以就学习了一下算法，并做一下笔记。废话不多说开始吧

---

找数

• 假设我们要在1到100中的一百个整数找一个指定大小的整数，要找多久呢？
  设这个数为10，若我们按顺序找
  A：是 1 ？
  B：小了
  A ：是 2 ？
  B : 小了
  …
  …
  A：是 10 ？
  B:对
  整个过程进行了十次，若我要找的数不是10，而是99，那不是要找99次，有没有一种更快的查找方法呢？
• 这次我们换一种方法找，假设我们要找60,。从50开始
  A：50 ？
  B：小了。（说明1-50都比这个数小）
  A：75 ？（在50-100中取中间数）
  B：大了。（说明这个数比75-100都小）
  A：62 ？（在50-75取中间数，向下取整，依次类推，直到找出那个数）
  B：大了。
  A：56 ？
  B：小了。
  A：59 ？
  B：小了。
  A：60？
  B：对了。
  每次A 同学猜测都是在已知最小数和最大数两者平均值猜测，直至最后结果。
  这样查找最多有多少步。
  100->50->25->12->6->3->1
  最多5步。
  在1-100这100个整数中，无论要查什么数，判断它是否存在这100个数中，最多需要5步。
• 若我们不止100个数，而是1000个，10000个，甚至上亿的数据。
  如果我们一个个查找，最多需要n次（n为数据总数），
  而换一种方法则是log2 N 次
  这就大量节省查找时间
• 这种查找方法就叫二分法查找。

---

二分法查找

#python3
def (list , item): #list必须是有序的
	high = len(list) - 1
	low = 0
	while low <= high:
		mid = int((high + low) / 2) #保证为整数，python默认向下取整
		if item >list[mid]:
			low = mid +1
		elif item < list[mid]:
			high = mid - 1
		else:
			return list[mid]
	return -1