28、数据结构与算法 - 实战：查找

无序线性查找(UnSorted Linear Search)
假设给定的一个数组，其元素的排列顺序是未知的，即数组中的元素是无序的。如果查找某个元素，必须扫描整个数组才能判断该元素是否在给定的数组中。

/**
 * 无序线性查找(UnSorted Linear Search)
 * @param array 给定的无序数组
 * @param data 需要查找的元素
 * @return 该元素在数组中的下标
 */
public static int unSortedLinearSearch(int[] array, int data) {
   
     
	for (int i = 0; i < array.length; i++) {
   
     
		if (array[i] == data) {
   
     
			return i;
		}
	}
	return -1;
}

无序线性查找(Sorted Linear Search)
假设给定的一个数组，其元素的排列顺序是已知的，即数组中的元素是有序的。如果A[i]的值大于要查找的值，直接返回-1，而不用扫描整个数组。

/**
 * 无序线性查找(Sorted Linear Search)
 * @param array 给定的有序数组
 * @param data 需要查找的元素
 * @return 该元素在数组中的下标
 */
public static int sortedLinearSearch(int[] array, int data) {
   
     
	for (int i = 0; i < array.length; i++) {
   
     
		if (array[i] == data) {
   
     
			return i;
		} else if(array[i] > data) {
   
     
			return -1;
		}
	}
	return -1;
}

二分查找是一个基础的算法，也是面试中常考的一个知识点。二分查找就是将查找的键和子数组的中间键作比较，如果被查找的键小于中间键，就在左子数组继续查找；如果大于中间键，就在右子数组中查找，否则中间键就是要找的元素。
参考：http://www.cnblogs.com/luoxn28/p/5767571.html

/**
 * 非递归二分查找算法
 * @param array 给定的有序数组
 * @param data 需要查找的元素
 * @return 该元素在数组中的下标
 */
public static int binarySearchIterative(int[] array, int data) {
   
     
	int mid = 0;
	int low = 0;
	int high = array.length - 1;
	while (low < high) {
   
     
	// 避免溢出
		mid = low + (high - low) / 2;
		if (array[mid] == data) {
   
     
			return mid;
		} else if (array[mid] > data) {
   
     
			high = mid - 1;
		} else {
   
     
			low = mid + 1;
		}
	}
	return -1;
}

/**
 * 二分查找算法(递归)
 * @param array 给定的有序数组
 * @param low 数组的起始位置
 * @param high 数组的结束位置
 * @param data 需要查找的元素
 * @return 该元素在数组中的下标
 */
public static int binarySearchRecursive(int[] array, int low, int high, int data) {
   
     
	if (low > high) {
   
     
		return -1;
	}
	// 避免溢出
	int mid = low + (high - low) / 2;
	if (array[mid] == data) {
   
     
		return mid;
	} else if (array[mid] > data) {
   
     
		return binarySearchRecursive(array, low, mid - 1, data);
	} else {
   
     
		return binarySearchRecursive(array, mid + 1, high, data);
	}
}

测试代码，敬请参考数据结构与算法(JAVA版)