二分查找的总结
思想还是要思考的..但是这个模板也是要记住的..毕竟考场如战场..唯快制胜..
/*
注意整个框架结构
*///寻找小于等于k的最大下标
int findLet(int x[], int n, int k)
{int l, r, m;l = 0;r = n - 1;while (l <= r){m = (l + r) / 2;if (x[m] <= k)l = m + 1;elser = m - 1;}return r;
}//寻找严格小于k的最大下标
int findLt(int x[], int n, int k)
{int l, r, m;l = 0;r = n - 1;while (l <= r){m = (l + r) / 2;if (x[m] < k)l = m + 1;elser = m - 1;}return r;
}//大于等于k的最小下标
int findGet(int x[], int n, int k)
{int l, r, m;l = 0;r = n - 1;while (l <= r){m = (l + r) / 2;if (x[m] >= k)r = m - 1;elsel = m + 1;}return l;
}//严格大于
int findGt(int x[], int n, int k)
{int l, r, m;l = 0;r = n - 1;while (l <= r){m = (l + r) / 2;if (x[m] > k)r = m - 1;elsel = m + 1;}return l;
}
注意重点区域的符号..然后再思考下二分的概念..
二分相当有用了..
更多推荐
二分查找的总结
发布评论