這么簡單的算法，九成程序員寫的都不對！

時間：2021-04-26 20:11:59

關(guān)鍵字：算法二分法程序員

手機(jī)看文章

掃描二維碼
隨時隨地手機(jī)看文章

[導(dǎo)讀]前段時間，在論壇上看到有統(tǒng)計說“90%的程序員都不能夠?qū)憣唵蔚亩址ā?。這？？？

前段時間，在論壇上看到有統(tǒng)計說“90%的程序員都不能夠?qū)憣唵蔚亩址?/span>”。這？？？?

其實，二分法真的不那么簡單，尤其是二分法的各個變種。

最最簡單的二分法，就是從一個排好序的數(shù)組之查找一個key值，如下面的程序：

/** * 二分查找，找到該值在數(shù)組中的下標(biāo)，否則為-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;}

這個程序，相信只要是一個合格的程序員應(yīng)該都會寫。稍微注意一點(diǎn)，每次移動left和right指針的時候，需要在mid的基礎(chǔ)上+1或者-1，防止出現(xiàn)死循環(huán)，程序也就能夠正確的運(yùn)行。

但如果條件稍微變化一下，你還會寫嗎？如，數(shù)組之中的數(shù)據(jù)可能可以重復(fù)，要求返回匹配的數(shù)據(jù)的最?。ɑ蜃畲螅┑南聵?biāo)；更近一步，需要找出數(shù)組中第一個大于key的元素（也就是最小的大于key的元素的）下標(biāo)，等等。這些，雖然只有一點(diǎn)點(diǎn)的變化，實現(xiàn)的時候確實要更加的細(xì)心。

下面，列出了這些二分檢索變種的實現(xiàn)。

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;}