C经典算法之二分查找法分享

—-想了解C经典算法之二分查找法分享的全部内容且更多的C语言教程关注<计算机技术网(www.ctvol.com)!!>

C经典算法之二分查找法

1.根据key查找所在数组的位置

  #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 = %dn", 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.插入一个数，得到其所在数组的位置

  #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 = %dn", 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插入到这个数的后面     return mid + 1;    }     }   //如果low > high 说明 key > arr[mid];   //就把key插入到low对应的 这个数的位置   return low;  }    

如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！