顺序查找
顺序查找又称为线性查找，是一种最简单的查找方法。适用于线性表的顺序存储结构和链式存储结构，从第一个元素开始逐个与需要查找的元素x进行比较，当比较到元素值相同时，返回元素m的下标，如果比较到最后都没有找到，则返回-1；
时间复杂度为O(n)
点击查看代码
public static void main(String[] args) {
int[] array = {12, 3, 43, 5, 9};
int target = 43;
int[] newArray = new int[array.length + 1];
newArray[0] = target;
for (int i = 0; i < array.length; i++) {
newArray[i + 1] = array[i];
}
}
//顺序查找 封装方法
/*private static int sequenceSearch(int[] array, int target) {
for (int i = 0; i < array.length; i++) {
if (target == array[i]) {
return i;
}
}
return -1;
}*/
优化
面对大量数据时，常常要使用预处理或者清洗操作
将要查询的数据放到新数组的第一个，然后将要查询的数组放入新数组进行查询
//查询方法，从最后一位元素往前查询，一直到第一个
public static int sequenceSearchPlus(int[] arr, int key) {
int n = arr.length - 1;
arr[0] = key;
while (arr[n] != key) {
n--;
}
return n;
}
}
二分查找
/*
* 在有序数组中查找某一特定元素的查找算法
*用给定k值先于中间节点的关键字比较，中间节点把线性表分为两个子表，若相等
* 则查找成功；若不相等，再根据k与该中间节点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点
* 折半搜索每次将搜索区域减少一半，时间复杂度为O(logn)
* 空间复杂度O(1)
*
* 当查找表不会频繁更新，删除操作时，使用折半查找是比较理想的
* 如果查找表有频繁的更新，删除操作，维护表的有序会花费比较大的精力，不建议使用该查找方式
* */
点击查看代码
static int binarySearch1(int arr[], int len, int target) {
//初始化左右搜索边界
int left = 0, right = len - 1;
int mid;
while (left <= right) {
//中间位置:两边界元素之和/2 向下取整
mid = (left + right) / 2;
//arr[mid] 大于target,即要寻找的元素在左半边，所以需要设定右边界为mid-1，搜索左半边
if (target < arr[mid]) {
right = mid - 1;
//arr[mid]小于target，即要寻找的元素在右半边，所以需要设定左边界为mid+1，搜索右半边
} else if (target > arr[mid]) {
left = mid + 1;
//搜索到对应元素
} else if (target == arr[mid]) {
return mid;
}
}
return -1;
}
递归法
点击查看代码
static int binarySearch2(int array[], int left, int right, int target) {
if (left <= right) {
int mid = (left + right) / 2;
if (array[mid] == target) {
return mid;
} else if (array[mid] < target) {
return binarySearch2(array, mid + 1, right, target);
} else {
return binarySearch2(array, left, mid - 1, target);
}
} else {
return -1;
}
}