无序线性查找(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版)