从数组中查找任何一个数字所在的位置（索引）

方式一：

/*
 * 从数组中查找9是在哪个位置，使用这种方式效率比较低
 */
package com.array;

public class ArraySearchTest {

	public static int search(int[] array, int value) {
		
		for(int i = 0; i < array.length; i++) {
			
			if(value == array[i]) {   //判断9是否与数组的索引相等
				return i;           //返回索引
			}
		}
		
		return -1;
	}
	
	public static void main(String[] args) {
		
		int[] a = new int[]{1,5,6,7,10,3,9};
		
		int value = 9;
		
		int index = search(a,value);
		
		System.out.println(index);
	}

}

总结：通过上面的查找方式发现，效率比较低，当数组元素是几千几万个的时候，要进行一个一个的比较，这种方式是非常低的;这种方式只适合,数组元素比较少的情况下，才适合

方式二：使用二分查找 高效查找数组元素的索引

二分查找法实现原理：
（1） 必须是有序的
（2） 将一组元素，一分为二
对1,3,5,6,7,8,10,12,15,16,19,22,23,25,27查找出25这个元素

分析：（1）这一组元素它总共是15个元素，一分为二之后，左边7个(1,3,5,6,7,8,10,)，右边7个(15,16,19,22,23,25,27)，中间就是第8个元素所对应的数字是12，因为12<25，所以把12之前的数字包括12本身全都过滤掉
（2）因为已经把12之前的数字包括12本身都过滤掉了，所以剩下15,16,19,22,23,25,27这7个元素，又把7一分为二，左边3个(15,16,19)，右边3个(23,25,27)，中间只剩下22，把22与25比较，因为22<25，所以把22之前的数字包括22本身过滤掉
（3） 最后只剩下23,25,27这三个元素，再一分为二，取中间元素25，就是我们要找的数字
请看下面代码：

package com.array;

public class ArraySearchTest1 {

	public static int binarySearch(int[] array,int value) {
		
		int low = 0;                   //low为数组下标的第一个元素
		int high = array.length - 1;  //high为数组下标最后一个元素
		int middle;                  //定义中间元素
		
		while(low <= high) {
			
			middle = (low + high) /2;    //取第一次中间的元素
			
			if(array[middle] == value) {
				return middle;
			}
			
			if(value < array[middle]) {
				high = middle - 1;
			}
			
			if(value > array[middle]) {
				low = middle + 1;
			}
		}
		
		return -1;
	}
	
	public static void main(String[] args) {

		int[] a = new int[]{1,3,5,6,7,8,10,12,15,16,19,22,23,25,27};
		
		int value = 25;
		
		int index = binarySearch(a,value);
		
		System.out.println(index);
	}

}

评论

1 楼 q694119254 2012-08-07  

你个2人  数组没排序怎么办