这么简单的算法,九成程序员写的都不对!

嵌入式ARM 2021-05-14 08:55


在论坛上看到有统计说“90%的程序员都不能够写对简单的二分法”。这??? 



其实,二分法真的不那么简单,尤其是二分法的各个变种。

最最简单的二分法,就是从一个排好序的数组之查找一个key值,如下面的程序:

/** * 二分查找,找到该值在数组中的下标,否则为-1 */static int binarySearch(int[] array, int key) {    int left = 0;    int right = array.length - 1;
// 这里必须是 <= while (left <= right) { int mid = (left + right) / 2; if (array[mid] == key) { return mid; } else if (array[mid] < key) { left = mid + 1; } else { right = mid - 1; } }
return -1;}

这个程序,相信只要是一个合格的程序员应该都会写。稍微注意一点, 每次移动left和right指针的时候,需要在mid的基础上+1或者-1, 防止出现死循环, 程序也就能够正确的运行。

但如果条件稍微变化一下, 你还会写吗?如,数组之中的数据可能可以重复,要求返回匹配的数据的最小(或最大)的下标;更近一步, 需要找出数组中第一个大于key的元素(也就是最小的大于key的元素的)下标,等等。这些,虽然只有一点点的变化,实现的时候确实要更加的细心。

下面,列出了这些二分检索变种的实现。

1、找出第一个与key相等的元素

// 查找第一个相等的元素static int findFirstEqual(int[] array, int key) {    int left = 0;    int right = array.length - 1;
// 这里必须是 <= while (left <= right) { int mid = (left + right) / 2; if (array[mid] >= key) { right = mid - 1; } else { left = mid + 1; } } if (left < array.length && array[left] == key) { return left; }
return -1;}

2、找出最后一个与key相等的元素

// 查找最后一个相等的元素static int findLastEqual(int[] array, int key) {    int left = 0;    int right = array.length - 1;
// 这里必须是 <= while (left <= right) { int mid = (left + right) / 2; if (array[mid] <= key) { left = mid + 1; } else { right = mid - 1; } } if (right >= 0 && array[right] == key) { return right; }
return -1;}

3、查找第一个等于或者大于Key的元素

// 查找第一个等于或者大于key的元素static int findFirstEqualLarger(int[] array, int key) {    int left = 0;    int right = array.length - 1;
// 这里必须是 <= while (left <= right) { int mid = (left + right) / 2; if (array[mid] >= key) { right = mid - 1; } else { left = mid + 1; } } return left;}

4、查找第一个大于key的元素

// 查找第一个大于key的元素static int findFirstLarger(int[] array, int key) {    int left = 0;    int right = array.length - 1;
// 这里必须是 <= while (left <= right) { int mid = (left + right) / 2; if (array[mid] > key) { right = mid - 1; } else { left = mid + 1; } } return left;}

5、查找最后一个等于或者小于key的元素

// 查找最后一个等于或者小于key的元素static int findLastEqualSmaller(int[] array, int key) {    int left = 0;    int right = array.length - 1;
// 这里必须是 <= while (left <= right) { int mid = (left + right) / 2; if (array[mid] > key) { right = mid - 1; } else { left = mid + 1; } } return right;}

6、查找最后一个小于key的元素

// 查找最后一个小于key的元素static int findLastSmaller(int[] array, int key) {    int left = 0;    int right = array.length - 1;
// 这里必须是 <= while (left <= right) { int mid = (left + right) / 2; if (array[mid] >= key) { right = mid - 1; } else { left = mid + 1; } } return right;}

接下来,大家可以对这四种变种算法进行相应的测试。

很多的时候,应用二分检索的地方都不是直接的查找和key相等的元素,而是使用上面提到的二分检索的各个变种,熟练掌握了这些变种,当你再次使用二分检索的检索的时候就会感觉的更加的得心应手了。


END


版权归原作者所有,如有侵权,请联系删除。

推荐阅读
你怎样选择开源免费RTOS?
GD32也开始假货翻新泛滥了
工程师姓什么很重要!别再叫我“X工”!!!


→点关注,不迷路←
嵌入式ARM 关注这个时代最火的嵌入式ARM,你想知道的都在这里。
评论 (0)
热门推荐
X
广告
我要评论
0
6
点击右上角,分享到朋友圈 我知道啦
请使用浏览器分享功能 我知道啦