這么簡(jiǎn)單的算法，九成程序員寫(xiě)的都不對(duì)！
[導(dǎo)讀]前段時(shí)間，在論壇上看到有統(tǒng)計(jì)說(shuō)“90%的程序員都不能夠?qū)憣?duì)簡(jiǎn)單的二分法”。這？？？
/*** 二分查找，找到該值在數(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;}
1、找出第一個(gè)與key相等的元素
// 查找第一個(gè)相等的元素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、找出最后一個(gè)與key相等的元素
// 查找最后一個(gè)相等的元素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、查找第一個(gè)等于或者大于Key的元素
// 查找第一個(gè)等于或者大于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、查找第一個(gè)大于key的元素
// 查找第一個(gè)大于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、查找最后一個(gè)等于或者小于key的元素
// 查找最后一個(gè)等于或者小于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、查找最后一個(gè)小于key的元素
// 查找最后一個(gè)小于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;}
免責(zé)聲明：本文內(nèi)容由21ic獲得授權(quán)后發(fā)布，版權(quán)歸原作者所有，本平臺(tái)僅提供信息存儲(chǔ)服務(wù)。文章僅代表作者個(gè)人觀(guān)點(diǎn)，不代表本平臺(tái)立場(chǎng)，如有問(wèn)題，請(qǐng)聯(lián)系我們，謝謝！
下載文檔
