您好,登錄后才能下訂單哦!
這篇文章主要介紹C經(jīng)典算法之二分查找法的示例分析,文中介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們一定要看完!
C經(jīng)典算法之二分查找法
1.根據(jù)key查找所在數(shù)組的位置
#include <stdio.h> /* key = 9; 1 2 3 4 5 6 7 8 arr 3, 4, 5, 7, 9 , 11, 21, 23 low = 1 mid = (low + high)/2 = 4 high = 8; one arr[mid] = 7 < 9; so low = mid + 1 = 5; high = 8; mid = (low + high)/2 = 6 two arr[mid] = 11 > 9 so low = 5 , high = mid - 1 = 5 mid = 5; arr[mid] = 9 == key if(key = 10) low = mid + 1 > high */ int main(int argc, const char * argv[]) { int findByHalf(int arr[], int len, int key); int arr[] = {3, 4 , 5, 7, 9 , 11, 21, 23}; int len = sizeof(arr)/sizeof(int); int index = findByHalf(arr, len, 88); printf("index = %d\n", index); return 0; } int findByHalf(int arr[], int len, int key){ int low = 0; int high = len - 1; int mid ; while(low <= high){ mid = (low + high) / 2; //右邊查找 if (key > arr[mid]) { low = mid + 1; //左邊查找 }else if (key > arr[mid]) { high = mid - 1; }else{ return mid; } } return -1; }
2.插入一個數(shù),得到其所在數(shù)組的位置
#include <stdio.h> /* key = 9; 1 2 3 4 5 6 7 8 arr 3, 4, 5, 7, 9 , 11, 21, 23 low = 1 mid = (low + high)/2 = 4 high = 8; one arr[mid] = 7 < 9; so low = mid + 1 = 5; high = 8; mid = (low + high)/2 = 6 two arr[mid] = 11 > 9 so low = 5 , high = mid - 1 = 5 mid = 5; arr[mid] = 9 == key if(key = 10) low = mid + 1 > high */ int main(int argc, const char * argv[]) { int findByHalf(int arr[], int len, int key); int arr[] = {3, 4 , 5, 7, 9 , 11, 21, 23}; int len = sizeof(arr)/sizeof(int); int index = findByHalf(arr, len, 88); printf("index = %d\n", index); return 0; } int insertByHalf(int arr[], int len, int key){ int low = 0; int high = len - 1; int mid ; while(low <= high){ mid = (low + high) / 2; //右邊查找 if (key > arr[mid]) { low = mid + 1; //左邊查找 }else if (key > arr[mid]) { high = mid - 1; }else{ //如果arr[mid] == key //就把key插入到這個數(shù)的后面 return mid + 1; } } //如果low > high 說明 key > arr[mid]; //就把key插入到low對應(yīng)的 這個數(shù)的位置 return low; }
以上是“C經(jīng)典算法之二分查找法的示例分析”這篇文章的所有內(nèi)容,感謝各位的閱讀!希望分享的內(nèi)容對大家有幫助,更多相關(guān)知識,歡迎關(guān)注億速云行業(yè)資訊頻道!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。