JDK学习之查找算法

今天我们学习两种常用的查找算法：顺序查找和折半查找，废话少说，先上代码，稍后分析：

 

1.下边是两种查找算法，其中第二种取自JDK源码：

 

    顺序查找

 

public static int sequentialSearch(int[] arrays, int key) {
		//声明返回的数组下标
		int index = -1;
		//声明查找标志位，提高查找速度
		boolean found = false;
		
		for (int i = 0; (i < arrays.length) & !found; i++) {
			if (arrays[i] == key) {
				found = true;
				index = i;

			}

		}

		return index;

	}

 

   折半查找，取自JDK中Arrays.binarySearch(int[] a, int key) :

 

	 public static int binarySearch(int[] a, int key) {
		                //声明数组的最小值和最大值
			int low = 0;
			int high = a.length-1;			
			
			while (low <= high) {
		                    //去low与high和中间值的index，将数值赋给midVal
			    int mid = (low + high) >> 1;
			    int midVal = a[mid];
		                    //用midVal跟key比较大小，如果小于key，则将mid+1赋给low,如果大于key，则将
		             //mid-1赋给high，否则就直接返回mid(等于key)
			    if (midVal < key)
				low = mid + 1;
			    else if (midVal > key)
				high = mid - 1;
			    else
				return mid; // key found
			}
			return -(low + 1);  // key not found.
		    }

 

2.典型应用：

 

同样，直接上代码：

public class ArraysTest {

	public static int sequentialSearch(int[] arrays, int key) {
		//声明返回的数组下标
		int index = -1;
		//声明查找标志位，提高查找速度
		boolean found = false;
		
		for (int i = 0; (i < arrays.length) & !found; i++) {
			if (arrays[i] == key) {
				found = true;
				index = i;

			}

		}

		return index;  // key not found.;

	}
	
	
	public static void main(String[] args) {

		int[] compartorIntArray = new int[3];
		compartorIntArray[0] = 1;
		compartorIntArray[1] = 2;
		compartorIntArray[2] = 3;
		System.out.println(ArraysTest.sequentialSearch(compartorIntArray, 3));
		System.out.println(ArraysTest.sequentialSearch(compartorIntArray, 8));
		System.out.println(Arrays.binarySearch(compartorIntArray, 3));
		System.out.println(Arrays.binarySearch(compartorIntArray, 8));
	}

}

 

执行结果：

 

2
-1
2
-4

 

3.总结

我们从上边可以看到，顺序查找的最小查找时间为O(1)，最大查找时间为O(n)，平均时间复杂度为((n+1)/2)

这里我们要注意，折半查找，必须应用在有序数组并且不是线性链表，无序数组，执行前需要预先进行排序，

平均时间复杂度近似为log(2)[n+1] -1,要比顺序查找的((n+1)/2)高效得多。

 

备注：很多程序员对于时间复杂度和空间复杂度的概念不是很了解，我学习的时候也查看了很多书籍，这里我建议

大家不要对其过度钻研，尤其是做企业开发的程序员，最好能大概记住每个算法的时间复杂度，可以在实际应用中

进行合理的选择，如果真的需要研究，建议先复习一下高等数学。 

 

这里还有一个疑问，为什么JDK中的折半查找，最后返回值是 -(low +1)呢，如果是没查到任何值，我可以直接返回 常量 -1，

这样做有什么优势吗？

 

评论

1 楼 snowolf 2010-04-13  

引用

我们从上边可以看到，顺序查找的最小查找时间为O(1)，最大查找时间为O(n)，平均时间复杂度为((n+1)/2)

这里我们要注意，折半查找，必须应用在有序数组并且不是线性链表，无序数组，执行前需要预先进行排序，

平均时间复杂度近似为log(2)[n+1] -1,要比顺序查找的((n+1)/2)高效得多。

呵呵，还可以继续举例论证修改时的时空复杂度～～，继续关注！