天津通用网站建设收费,阿里云wordpress扩容,求一个全部用div做的网站,wordpress小程序搭建文章目录 什么是二分法#x1f3ae;二分查找的优先级二分查找的步骤#x1f4a5;图解演示#x1f9e9; 代码演示#x1fad5;python程序实现#x1f408;⬛C程序实现#x1f415;#x1f9ba;C程序实现#x1f42f;Java程序实现#x1f433; 非常规类二分查找二分查找的优先级二分查找的步骤图解演示 代码演示python程序实现⬛C程序实现C程序实现Java程序实现 非常规类二分查找查找有序列表中某数首次出现的位置 什么是二分法
二分法(Bisection method)即一分为二的的方法。数学的零点估计问题中对于在区间[a,b]上连续不断且满足 f(a) * f(b) 0的函数yf(x),通过不断地把函数f(x)的零点所在区间二等分使区间两个端点逐步逼近零点进而得到零点的近似值的方法。 当然在我们技术人的手中一般是用来解决有序列表中查找某个元素的问题属于搜索方法的一种。 简单的来说就是将答案所在的区间不断缩小为原来的 1/2直到找到答案。 类似二分法的实例假如你和朋友在玩猜数字游戏朋友记录一个数规定数的范围你来猜。你每猜一个数朋友会告诉你这个数大了还是小了直到你猜出正确答案为止。假如有100个数你一个一个数猜你最差的情况需要找100次如果你使用二分的思想查找每次折半最多只需要7次即可猜出答案。
二分查找的优先级
二分查找算法的时间复杂度为O(log n)因此其优先级较高适合在需要快速查找有序列表中的元素时使用。相比于线性查找算法的时间复杂度为O(n)二分查找算法具有更高的效率尤其适用于数据量较大的情况。同时二分查找算法较为简单易于实现和理解因此被广泛应用于各个领域的程序设计中。 二分查找的效率虽然高但只局限于有序列表
二分查找的步骤
二分查找的思路是先取中间位置的值进行比较如果该值等于目标值则查找成功否则如果该值大于目标值则在左半部分继续查找如果该值小于目标值则在右半部分继续查找。不断重复以上步骤直到找到目标值或者确定目标值不存在为止。
图解演示
在下面这个有序数组中查找数字3定义三个指针left、right、mid 这三个指针都是动态的left 为左边界的下标right 为右边界的下标mid(leftright)/2 arr[mid]3中间值大于目标值说明右边没有要查找的数之后范围缩小到左边。改变右指针rightmid-1这里 arr[mid] 恰好等于要查找的数二分结束。假设要查找的数变为4那么还需要继续查找如图 arr[mid]4中间值小于目标值说明左边没有要查找的数范围再缩小到原来的右边 改变左指针leftmid1 arr[mid]4 就找到了需要查找的数当左指针 left 大于等于右指针 right 时二分查找结束答案可能是找到目标值或者目标值不存在。
代码演示
其中arr为有序列表target为需要查找的元素最终未找到就返回 -1
python程序实现⬛
def binary_search(arr, target):left, right 0, len(arr) - 1while left right:mid (left right) // 2if arr[mid] target:return midelif arr[mid] target:left mid 1else:right mid - 1return -1
定义一个函数binary_search该函数接受两个参数一个有序数组 arr 和要查找的目标元素 target
C程序实现
#include stdio.h// 二分查找函数
int binary_search(int arr[], int left, int right, int target){while (left right) // 当leftright时停止查找{int mid (left right) / 2; // 计算中间位置if (arr[mid] target) // 找到目标值{return mid;}else if (arr[mid] target) // 目标值在右半部分{left mid 1;}else // 目标值在左半部分{right mid - 1;}}return -1; // 没有找到目标值
}int main()
{int arr[] {1, 3, 5, 7, 9, 11}; // 有序数组int n sizeof(arr) / sizeof(arr[0]); // 数组长度int target 5; int index binary_search(arr, 0, n - 1, target); // 进行二分查找if (index -1){printf(目标值不存在\n);}else{printf(目标值在数组中的下标为%d\n, index);}return 0;
}自己定义一个函数binary_search接收数组、数组的左右边界下标或数组元素个数以及要查找的元素
C程序实现
#include iostream
using namespace std;int binarySearch(int arr[], int l, int r, int x) {if (r l) {int mid l (r - l) / 2;if (arr[mid] x) {return mid;}if (arr[mid] x) {return binarySearch(arr, l, mid - 1, x);}return binarySearch(arr, mid 1, r, x);}return -1;
}int main() {int arr[] { 2, 4, 6, 8, 10 };int n sizeof(arr) / sizeof(arr[0]);int x 8;int result binarySearch(arr, 0, n - 1, x);if (result -1) {cout Element not found endl;}else {cout Element found at index result endl;}return 0;
}
函数binarySearch为二分查找函数该函数接受一个整数数组数组的左右边界以及要查找的元素
Java程序实现
public class BinarySearch {int binarySearch(int arr[], int l, int r, int x) {if (r l) {int mid l (r - l) / 2;if (arr[mid] x) {return mid;}if (arr[mid] x) {return binarySearch(arr, l, mid - 1, x);}return binarySearch(arr, mid 1, r, x);}return -1;}public static void main(String args[]) {BinarySearch bs new BinarySearch();int arr[] { 2, 4, 6, 8, 10 };int n arr.length;int x 8;int result bs.binarySearch(arr, 0, n - 1, x);if (result -1) {System.out.println(Element not found);}else {System.out.println(Element found at index result);}}
}
在此示例中定义了一个类BinarySearch其中包含一个递归函数binarySearch该函数接受一个整数数组数组的左右边界以及要查找的元素。
非常规类二分查找
查找有序列表中某数首次出现的位置
如下图中找到3首次出现的位置左边界不难。但要以时间复杂度为 log(N)找到就要采用二分查找了。 C程序代码
int Find_Edges(int*nums,int len,double k)
{int left0,rightlen-1;while(leftright){int mid(leftright)/2;if(nums[mid]k)leftmid1;else if(nums[mid]k)rightmid-1;}return left;
}int GetNumberOfK(int* nums, int numsLen, int k ) {return Find_Edges(nums,numsLen,k-0,5);
}上面这段代码将参数 3-0.5 传上去就可以求出3的左边界因为传上去的是浮点数那肯定是找不到的只能找到距离最近的向上取整的可以找到的数因为整数除法是向下取整的所以mid的值一定是小于等于 (leftright)/2的所以一定会在 left 位置结束二分查找。 同样将参数 30.5 传上去就可以求出3的右边界进而求出这个数组中一共有多少个3进而解决这篇博客中最后一题C语言笔试训练。
