本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论
算法(第4版)
知识点
- 等值键
1.1.29 等值键。为 BinarySearch 类添加一个静态方法 rank()，它接受一个键和一个整型有序数组(可能存在重复键)作为参数并返回数组中小于该键的元素数量，以及一个类似的方法 count() 来 返回数组中等于该键的元素的数量。注意:如果 i 和 j 分别是 rank(key,a) 和 count(key,a) 的返回值，那么 a[i..i+j-1] 就是数组中所有和 key 相等的元素。
1.1.29 Equal keys. Add to BinarySearch a static method rank() that takes a key and a sorted array of int values (some of which may be equal) as arguments and returns the number of elements that are smaller than the key and a similar method count() that returns the number of elements equal to the key. Note : If i and j are the values returned by rank(key, a) and count(key, a) respectively , then a[i..i+j-1] are the values in the array that are equal to key.
分析
二分法查找的一个使用案例
答案
见小专栏 点击这里跳转
广告
我的首款个人开发的APP壁纸宝贝上线了，欢迎大家下载。
网友评论
count的话：可以通过rank获取到该元素的第一个位置，然后向后遍历，直到与所查找的key不同的数。
这样就把二分查找的优势利用了，缩小了查找的范围，而不是从头开始遍历。
resultNum ++;
}
而count函数中，if (array[i] == array[searchResult]) {
resultNum ++;
}
才是题目的表达的意思，并且这两个函数，你在书写过程是重复的，如果表达不当地方还请见谅，可能也是我理解错了。
这题 我想了个 你看看
public static int rank(int[] a, int key) {
int lo = 0;
int hi = a.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
StdOut.println(mid+" "+lo+" "+hi);
if(key==a[0]) return 0;
else if(key>a[a.length-1]) return a.length;
else if (key < a[mid]) hi = mid - 1;
else if (key > a[mid]) lo = mid + 1;
else if (mid!=0) {
if(key==a[mid-1]) hi=mid;
else return mid;
}
}
return -1;
}
public static int count (int key,int[] a) {
int c=0;
int i=rank(a, key);
if(i<0 || key>a[a.length-1]) return 0;
else
while(key==a[i+c] ) {
c++;
if(i+c==a.length) break;
}
return c;
}
测试没啥问题 但是总感觉哪里有问题 哈哈~