线性查找 (linear search)
public class LinearSearchDemo {
public static void main(String[] args) {
int[] data = {2, 1, 4, 6, 12, 7};
int target = 12;
int searchIndex = search(data, target);
if (searchIndex != -1) {
System.out.println("found at: " + searchIndex);
}else {
System.out.println("not found");
}
}
/*
*@param data 待查找的数组
*@param target 待查找的值
*@return int 目标值在数组中的索引,如果没找到返回-1
*/
public static int search(int[] data, int target) {
int length = data.length;
//从头遍历数组中的各个值,如果找到目标值就返回其索引
for (int i = 0; i < length; i++) {
if (data[i] == target) {
return i;
}
}
//代码能走到这一步就说明上面的循环遍历结束了也没找到目标值
//即目标值不存在于数组中
return -1;
}
}
二分查找 (binary search)
二分查找的关键点其实是数据顺序的有序,数据顺序不有序的话,用不了二分查找的
//二分查找:在有序数组中查找某一特定元素的搜索算法
public class BinarySearch {
public static void main(String[] args) {
int[] data = {1, 5, 6, 12, 15, 19, 23, 26, 30, 33, 37, 42, 53, 60};
int target = 19;
int index = binarySearch2(data, 0, data.length - 1, target);
if (index > -1) {
System.out.println("found :" + index);
}else {
System.out.println("not found");
}
}
/**
* 递归方法实现二分查找
* @param data 已排序数组(这里假设是从小到大排序)
* @param from 起始位置
* @param to 终止位置
* @param target 要查找的值
* @return 要查找的值在数组中的位置,如果没找到则返回-1
*/
private static int binarySearch1(int[] data, int from, int to, int target) {
if (from <= to) {
int mid = from + (to - from) / 2;//中间位置,为了防止溢出使用这种方式求中间位置
if (data[mid] < target) {//中间的值比目标值小,则在左半边继续查找
return binarySearch1(data, mid + 1, to, target);
}else if(data[mid] > target){//中间的值比目标值大,则在右半边继续查找
return binarySearch1(data, from, mid - 1, target);
}else {//找到了,把找到的情况放在最后是因为多数情况下中间值不是大于就是小于,这样做可以节省操作
return mid;
}
}
return -1;
}
/**
* 非递归方法实现二分查找
* @param data 已排序数组(这里假设是从小到大排序)
* @param from 起始位置
* @param to 终止位置
* @param target 要查找的值
* @return 要查找的值在数组中的位置,如果没找到则返回-1
*/
private static int binarySearch2(int[] data, int from, int to, int target) {
while(from <= to) {
int mid = from + (to - from) / 2;
if (data[mid] < target) {
from = mid + 1;
}else if(data[mid] > target) {
to = mid - 1;
}else {//找到了,把找到的情况放在最后是因为多数情况下中间值不是大于就是小于,这样做可以节省操作
return mid;
}
}
return -1;
}
}