网站建设服务器端软件,2023新闻摘抄十条,12333上海公共招聘网登录,网站开发和安卓开发文章出处#xff1a;极客时间《数据结构和算法之美》-作者#xff1a;王争。该系列文章是本人的学习笔记。
思考题目
1 用最省内存的方式查找数据。 2 快速定位ip所在省市
二分查找的速度
二分每次都通过跟区间中的中间元素对比#xff0c;将待查找的区间缩小为一半极客时间《数据结构和算法之美》-作者王争。该系列文章是本人的学习笔记。
思考题目
1 用最省内存的方式查找数据。 2 快速定位ip所在省市
二分查找的速度
二分每次都通过跟区间中的中间元素对比将待查找的区间缩小为一半直到区间为0或者找到元素。需要重点关注退出条件、mid取值、low和high的更新。
二分的时间复杂度O(logn)。logn少的惊人之处和指数的大的惊人之处类似。2的32次方是4亿多。在4亿多有序数组中查找数据只需要32次。很少吧。
简单代码实现
简单是因为数组中没有重复数据。 public static int easySearch(int[] a,int value){if(anull) return -1;int n a.length;int low 0;int high n-1;return easySearch(a, value, low, high);}private static int easySearch(int[] a,int value,int low,int high){if(lowhigh) return -1;int mid low ((high-low)1);if(valuea[mid]) return mid;if(valuea[mid]) return easySearch(a,value,low,mid-1);return easySearch(a,value,mid1,high);}二分的应用场景
1 二分依赖的是顺序表也就是数组。链表复杂度变高。因为链表随机查找的时间复杂度是O(n)。 如果使用链表第一次查找a[mid]需要n2\dfrac{n}{2}2n次查找第二次查找a[mid]需要n4\dfrac{n}{4}4n次查找依次类推所需要的查找有sumn2n4n8....1n−1sum\dfrac{n}{2}\dfrac{n}{4}\dfrac{n}{8}....1n-1sum2n4n8n....1n−1。时间复杂度O(n)。
2 二分针对的是有序数据。在插入、删除比较少的场景中可以将排序的时间成本均摊到查询上面。插入、删除多则复杂度升高。
3 数据量小不能体现二分的优势。例如10个数据。无论顺序查找还是二分时间差不多。
4 数据量不能太大。因为二分依赖数组存储数据数组要求连续的内存。
思考题
在100M内存中查找1000万整数的某个数。如果用long表示整数一个整数8个字节1000万整数80M内存。可以先使用空间复杂度低的排序算法排序之后二分查找。
求一个数的平方根精确到小数点后6位。
二分的变体
查找第一个等于value的元素的位置 public static int findFirstEqualElement(int[] a ,int value){if(anull) return -1;int n a.length;int low 0;int high n-1;while(lowhigh){int mid low ((high-low)1);if(valuea[mid]){high mid - 1;}else if(valuea[mid]){low mid 1;}else{if(mid0 || a[mid-1]!value)return mid;elsehigh mid-1;}}return -1;}最后一个等于value的元素的位置 public static int findLastEqualElement(int[] a ,int value){if(anull) return -1;int n a.length;int low 0;int high n-1;while(lowhigh){int mid low ((high-low)1);if(valuea[mid]){high mid - 1;}else if(valuea[mid]){low mid 1;}else{if(midn-1 || a[mid1]!value)return mid;elsehigh mid-1;}}return -1;}查找第一个大于等于value的元素的位置 public static int findFirstMoreOrEqualElement(int[] a ,int value){if(anull) return -1;int n a.length;int low 0;int high n-1;while(lowhigh){int mid low ((high-low)1);if(valuea[mid]){if(mid0 || a[mid-1]value) return mid;high mid - 1;}else if(valuea[mid]){low mid 1;}}return -1;}查找最后一个小于等于value的元素的位置
public static int findLastLessOrEqualElement(int[] a ,int value){if(anull) return -1;int n a.length;int low 0;int high n-1;while(lowhigh){int mid low ((high-low)1);if(valuea[mid]){high mid - 1;}else if(valuea[mid]){if(midn-1 || a[mid1]value)return mid;low mid 1;}}return -1;}思考题
快速定位ip所在省市。可以用一个32位的int表示一个ip地址。查找每一个ip段内最后一个起始ip小于等于目标ip的ip段然后查找目标ip是不是在这个范围内。
循环有序数据的二分查找怎么解决,数组是升序。 需要先找到第一个a[i]lt;a[i1]a[i]lt;a[i1]a[i]a[i1]例如数组nums{4,5,6,7,0,1,2}。i应该等于4。然后我们可以选择将数组复制一下成为{0,1,2,4,5,6,7}但是这样时间复杂度就会是O(n)。我们也可以这样看nums[4]0,nums[5]1,nums[6]2,nums[7]4,nums[8]5,nums[9]6,nums[10]6。相当于将nums看做是一个循环数组。 public int search(int[] nums, int target) {int n nums.length;int low 0;int high n-1;while(lowhigh){int mid (lowhigh)/2;if(nums[mid]nums[high]){low mid 1;}else{high mid;}}int rotatedIndex low;low 0;high n-1;while(lowhigh){int mid (lowhigh)/2;int realMid (midrotatedIndex)%n;if(nums[realMid]target){low mid1;}else if(nums[realMid]target){high mid-1;}else{return realMid;}}return -1;}
