龙岗做网站哪里找,网站管理与维护的优势,网站建设 科技公司,唐山做企业网站的公司如果要你在一个升序序列中查找一个值的位置#xff0c;你是否还会傻乎乎的用下面这个 O ( n ) \mathcal O(n) O(n) 的代码暴力查找#xff0c;如果是#xff0c;我告诉你#xff0c;其实根本不用这么做。
int find(int a[],int n,int k) {for(int i0;in;i) if(a[i]k)…如果要你在一个升序序列中查找一个值的位置你是否还会傻乎乎的用下面这个 O ( n ) \mathcal O(n) O(n) 的代码暴力查找如果是我告诉你其实根本不用这么做。
int find(int a[],int n,int k) {for(int i0;in;i) if(a[i]k) return i;
}猜数字这个游戏大家都玩过吧这里介绍以下规则
一名玩家在一个范围内想出一个数。这名玩家告诉其他玩家他所想的范围。其他玩家在这个范围内猜数若 猜中了该玩家获胜没猜中根据该玩家猜的数缩小范围然后接着进行操作 2。对于缩小范围设初始范围为 l ∼ y l\sim y l∼y要猜的数为 n n n猜的数位 n n n若 m n mn mn将范围缩小至 m ∼ r m\sim r m∼r。 m n mn mn将范围缩小至 l ∼ m l\sim m l∼m。
显然想要最快猜到该数就需要采用折半的方法去猜每次都猜这个范围的中间数。二分查找也是一样对于每一次查找都判断中间的数与要找的数的大小关系然后采取对应的操作。
需要注意的是二分查找需要保证序列是升序的。
这里放个代码
//循环版
int find(int a[],int n,int k) {int l0,rn-1;while(lr) {int mid(lr)/2;if(a[mid]k) rmid-1;else if(a[mid]k) lmid1;else if(a[mid]k) return mid;}return -1;
}
//递归版
int find(int a[],int n,int k,int l,int r) {if(lr) return -1;int mid(lr)/2;if(a[mid]k) return find(a,n,k,l,mid-1);else if(a[mid]k) return find(a,n,k,mid1,r);else if(a[mid]k) return mid;
}练习题洛谷 link
