二分查找的两种写法，递归和普通循环~ 大部分情况下都用普通的循环，因为递归法费空间。
/*
时间复杂度：
1.最坏情况 查找最后一个元素（或者第一个元素） Master定理 T(n)=T(n/2)+O(1) 这个O(1)是判断 所以 T(n)=O(logn)
a=1 b=2 所以要比较的是 O(1)和 n^(log2 1)
2.最好情况 查找中间元素O(1)
空间复杂度：
S(n)=n
*/int biFind(int* A,int len,int item,int cur){
//example: len 4: 2 4 5 3 middle = 1 (1.5)
//example: len 5: 2 5 6 4 1 middle = 2
int middle = (len-1)/2;
if (A[middle]==item)
return cur;
if (len==1)
return -1;
if(A[middle]>item)
return biFind(A, middle, item,cur);
return biFind(A+middle+1, len-middle-1, item,cur+middle+1);
}
int biFind_1(int* A,int x,int y,int item){
//划分
int m = x+(y-x)/2;
while (x
//lower_bound的定义 = 若A中有item 则返回A中item第一次出现的位置
//若没有item 则返回i:这个i可以是的 把A[i],A[i+1]...后遗 把item插入到A[i]可以保证A有序
int lower_bound(int* A,int x,int y,int item){
//划分
int m ;
while (x=item) y=m;
//找到了但是左面有可能还有 或者 中间元素大于item
else x=m+1;
//item在右边 所以左边更新为m+1
}
//如果一直没找到 此时x==y 且是正中间
return x;
}
【【算法学习笔记】22.算法设计初步 二分查找 上下界判断】
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- 算法学习笔记|【算法学习笔记】02.wikioi1205 单词翻转
- 算法学习笔记|【算法学习笔记】14.暴力求解法03 回溯法01 N皇后和素数环
- 解题报告|【算法学习笔记】23.动态规划 解题报告 SJTU_OJ 1280 整装待发
- 算法学习笔记|【算法学习笔记】19.算法设计初步 最大子列和问题的三种方法
- 算法学习笔记|【算法学习笔记】20.算法设计初步 归并排序 求逆序数
- 【算法学习笔记】15.暴力求解法04 回溯法02 困难的串