ToB企服应用市场:ToB评测及商务社交产业平台

标题: Java实现常见查找算法 [打印本页]

作者: 千千梦丶琪 时间: 2023-9-16 05:04
标题: Java实现常见查找算法
Java实现常见查找算法

查找是在大量的信息中寻找一个特定的信息元素，在计算机应用中，查找是常用的基本运算，例如编译程序中符号表的查找。
线性查找

线性查找（Linear Search）是一种简单的查找算法，用于在数据集中逐一比较每个元素，直到找到目标元素或搜索完整个数据集。它适用于任何类型的数据集，无论是否有序，但在大型数据集上效率较低，因为它的时间复杂度是 O(n)，其中 n 是数据集的大小。
以下是线性查找的基本步骤：

从数据集的第一个元素开始，逐一遍历每个元素。
比较当前元素与目标元素是否相等。
- 如果相等，表示找到了目标元素，返回当前元素的索引位置。
- 如果不相等，继续遍历下一个元素。
如果遍历完整个数据集都没有找到目标元素，则返回一个表示元素不存在的标识（如 -1）。

以下是使用Java实现线性查找的示例代码：

public class LinearSearch {
public static int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
return i; // 目标元素的索引位置
}
}
return -1; // 目标元素不存在于数组中
}
public static void main(String[] args) {
int[] arr = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int target = 23;
int result = linearSearch(arr, target);
if (result == -1) {
System.out.println("目标元素不存在于数组中");
} else {
System.out.println("目标元素的索引位置为: " + result);
}
}
}

复制代码

二分查找

二分查找算法（Binary Search）是一种高效的查找算法，用于在有序数组或列表中查找特定元素的位置。它的基本思想是通过将数组分成两半，然后确定目标元素在哪一半，然后继续在那一半中搜索，重复这个过程直到找到目标元素或确定不存在。
二分查找算法的时间复杂度是 O(log n)，其中 n 是数据集的大小。这使得它在大型有序数据集中的查找操作非常高效,每次将数据集分成两半，然后确定目标元素在哪一半，然后继续在那一半中搜索。每次操作都将数据集的规模减少一半，因此它的时间复杂度是对数级别的.
需要注意的是，二分查找算法要求数据集必须是有序的。如果数据集无序，需要先进行排序操作。排序操作通常具有较高的时间复杂度（如快速排序的平均时间复杂度为 O(n log n)），因此总体上二分查找算法加上排序操作的时间复杂度可能会更高。
总结起来，二分查找算法是一种高效且常用的查找算法，在大型有序数据集中具有较低的时间复杂度。
以下是二分查找算法的详细步骤：

初始化左指针 left 为数组的起始位置，右指针 right 为数组的结束位置。
计算中间位置 mid，即 mid = left + (right - left) / 2。
比较中间位置的元素与目标元素：
- 如果中间位置的元素等于目标元素，则返回中间位置。
- 如果中间位置的元素大于目标元素，则更新右指针 right = mid - 1，并回到步骤2。
  - 如果中间位置的元素小于目标元素，则更新左指针 left = mid + 1，并回到步骤2。
如果左指针大于右指针，则表示目标元素不存在于数组中。

以下是使用Java实现二分查找算法的示例代码（迭代法）：
[code]public class BinarySearch { public static int binarySearch(int[] arr, int target) { int left = 0;// 左指针，初始为数组起始位置 int right = arr.length - 1;// 右指针，初始为数组结束位置 while (left

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)