二分查找

######思想 在一个含有X个有序的元素序列中，查找一个元素n。第一步，判断中n跟X/2的元素比较。如果小了，则继续跟X/4比较。如果大了，则跟3/4X比较。直到找到元素n。时间复杂度为log₂X。

public class BinarySearch{
	
	int low;
	int hight;
	int length;
	
	public int GetIndexWithBinarySearch(int num,List<Integer> list) {
		length=list.size();
		low=0;
		hight=list.size();
		int  index=Find(low,hight,num,list);
		return index;
	}
	
	
	 int Find(int low,int heiht,int num,List<Integer> list) {
		int index=(low+hight)/2;
		if(num==list.get(index))
			return index;
		if(hight-low<=1&&num!=list.get(index))
			return -1;
		if(num>list.get(index))
		{
			low=index;
		}
		else {
			hight=index;
		}
		return Find(low,hight,num,list);
	}

#####时间复杂度O 大O表示法指出了算法有多快. 假设列表包含n个元素。简单查找需要检查每个元素，因此需要执行n次操作。使用大O表示法，这个运行时间为O(n) ######经常会遇到的5种大O运行时间。 O(log n)，也叫对数时间，这样的算法包括二分查找。 O(n)，也叫线性时间，这样的算法包括简单查找。 O(n * log n)，这样的算法包括第4章将介绍的快速排序——一种速度较快的排序算法。 O(n2)，这样的算法包括第2章将介绍的选择排序——一种速度较慢的排序算法。 O(n!)，这样的算法包括接下来将介绍的旅行商问题的解决方案——一种非常慢的算法。

旅行商问题

有一位旅行商。 他需要前往5个城市。这位旅行商要前往这5个城市，同时要确保旅程最短。为此，可考虑 前往这些城市的各种可能顺序。对于每种顺序，他都计算总旅程，再挑选出旅程最短的路线。5个城市有120种不同的排列方 式。因此，在涉及5个城市时，解决这个问题需要执行120次操作。涉及6个城市时，需要执行720 次操作（有720种不同的排列方式）。涉及7个城市时，需要执行5040次操作！推而广之，涉及n个城市时，需要执行n!（n的阶乘）次操作才能计算出结果。因此运行时间 为O(n!)，即阶乘时间。