简述顺序查找二分法查找的原理
时间: 2023-05-28 19:05:40 浏览: 76
顺序查找的原理是从第一个元素开始,逐个比较,直到找到匹配的元素或者遍历完整个数组。顺序查找的时间复杂度为O(n)。
二分法查找的原理是将有序数组分成两个部分,取中间元素进行比较,如果匹配则返回,否则根据比较结果确定下一次查找的区间,继续进行二分查找,直到找到匹配的元素或者区间缩小到为空。二分法查找的时间复杂度为O(log n)。
相关问题
二分法查找 java_java顺序查找和二分法查找
顺序查找(线性查找)是一种基本的查找算法,其原理是从数组的第一个位置开始逐个比较查找目标值,直到找到为止或者遍历完整个数组。这种方法的时间复杂度是O(n),其中n是数组的长度。
而二分法查找(折半查找)是一种更高效的查找算法,其适用于已排序的数组。它的原理是将数组一分为二,然后判断目标值在哪个子数组中,再在该子数组中进行查找。这种方法的时间复杂度是O(log n),其中n是数组的长度。
下面是Java实现的示例代码:
顺序查找:
```
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 int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
```
java折半查找二分法
折半查找(二分法)是一种用于在有序数组中查找特定元素的算法。以下是一个 Java 实现示例:
```java
public class BinarySearch {
public static int binarySearch(int[] array, int target) {
int left = 0;
int right = array.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (array[mid] == target) {
return mid; // 找到目标元素,返回索引
} else if (array[mid] < target) {
left = mid + 1; // 目标元素在右半部分,更新左边界
} else {
right = mid - 1; // 目标元素在左半部分,更新右边界
}
}
return -1; // 目标元素不存在,返回 -1
}
public static void main(String[] args) {
int[] array = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int target = 23;
int result = binarySearch(array, target);
if (result == -1) {
System.out.println("目标元素不存在");
} else {
System.out.println("目标元素在索引 " + result + " 处");
}
}
}
```
运行上述代码将输出:目标元素在索引 5 处