顺序查找的时间复杂度是O(n),如果数组一开始是有序的,那么用顺序查找的效率是比较低的,因为二分查找等方式能够拥有更低的时间复杂度,但是如果一开始是无序的,那么顺序查找有可能比其他查找更加的快速。
二分查找主要是应用在有序的数组织中,采取的是一种分治的思想,先在数组中去中值,然后将中值与查询的值进行比较,如果小,就在左边数组中查询,如果大,就在右边数组中查询,这样就缩小了查询的范围,同时在半个数组中还能进一步进行划分,能够加快查询的速度。
private static int a[] = {1,2,3,4,5,6,7,8}; //非递归 public static void binarySort(int low,int high,int c) { int mid =( low+high)/2; System.out.println("mid is "+mid+" and a[mid] is "+a[mid]); if(c==a[mid]){ System.out.println("find"); }else if(c<a[mid]){ high = mid-1; if(low<=high) binarySort(low,high,c); }else if(c>a[mid]){ low = mid+1; if(low<=high) binarySort(low,high,c); } } //递归 public static void binarySorts(int low,int high,int c) { while(low<=high){ int mid =( low+high)/2; if(c==a[mid]){ System.out.println("find"); break; }else if(c<a[mid]){ high = mid-1; }else if(c>a[mid]){ low = mid+1; } } }
分别采用递归和非递归的方式进行了实现。
原文:http://www.cnblogs.com/cjmlovelulu/p/3724309.html