算法 – 二分法
二分法
简介
二分法是一种在有序数列中查找某一特定元素的搜索算法
基本思路
首先,从有序数列的中间位置开始搜索,如果该位置的值比目标值小,则在数列的右半部分继续搜索;如果该位置的值比目标值大,则在数列的左半部分继续搜索。这样递归进行,直到找到目标值,或者搜索完整个数列仍然没有找到目标值为止。
时间复杂度
二分法的时间复杂度为O(log n),这使得它成为在有序数列中查找某一特定元素的一种非常高效的算法。
案例
int binarySearch(int array[], int target, int low, int high) {
if (low > high) {
return -1; // 搜索失败
}
int mid = (low + high) / 2;
if (array[mid] == target) {
return mid; // 搜索成功
} else if (array[mid] < target) {
return binarySearch(array, target, mid + 1, high); // 搜索右半部分
} else {
return binarySearch(array, target, low, mid - 1); // 搜索左半部分
}
}
array 数组是搜索的有序数列,target 是要查找的目标值,low 和high分别表示搜索范围内的最大值和最小索引值。
版权声明:本文为qq_26183767原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。