Nullreference Q&A 编程技术问答社区
第一次访问本站?请查看 FAQ!
x
+2 投票
165 浏览

用c语言实现折半查找法。

最新提问 5月 17, 2016 分类:C | 用户: ativie | 165 浏览

2 个回答

+2 投票
已采纳

也可以用递归法实现

#include <stdio.h>
 
// 递归法实现二分搜索
// l 查找的起始位置,r 查找的结束位置,x 查找的值
int binarySearch(int arr[], int l, int r, int x)
{
   if (r >= l)
   {
        int mid = l + (r - l)/2;
 
        // 找到
        if (arr[mid] == x)  return mid;
 
        // 从前半部分查找
        if (arr[mid] > x) return binarySearch(arr, l, mid-1, x);
 
        // 从后半部分查找
        return binarySearch(arr, mid+1, r, x);
   }
 
   // 未找到
   return -1;
}
 
int main(void)
{
   int arr[] = {1, 3, 5, 10, 20, 25, 30, 40};
   int n = sizeof(arr) / sizeof(arr[0]);
   int result = binarySearch(arr, 0, n-1, 20);
   printf("index is %d", result );
   return 0;
}
最新回答 5月 17, 2016 用户: snoopy (1,760 分)
采纳于 5月 19, 2016 用户:Walt
+1 投票

折半查找法又叫二分法或二分搜索法,是一个快速从有序数组中查找给定值的算法。主要思想是:首先从数组的中间查找,如果相等则结束查找;如果给定的值小于中间的值,则接着用折半查找法从前半部分查找;如果给定的值大于中间的值,则接着用折半查找法从后半部分查找。
下面是 C 语言代码:

#include  <stdio.h>

int main(void)
{
    int myArray[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    int i = binarySearch(myArray, 6);
    printf("index is [%d]", i );
    return 0;
}

int binarySearch(int sortedArray[], int value) {  
    int first = 0;
    int last = sizeof(sortedArray);
    
    while (first <= last) {
       int mid = (first + last) / 2;  // 计算中点
       if (value > sortedArray[mid]) 
           first = mid + 1;  // 从后半部分查找
       else if (value < sortedArray[mid]) 
           last = mid - 1; // 从前半部分查找
       else
           return mid;     // 找到,返回索引
    }
    return -1;    // 未找到
}

在线运行 http://rextester.com/live/IWAL54304

最新回答 5月 17, 2016 用户: Walt (1,190 分)
@Walt 代码中有一处错误,C语言中数组传参数时是按指针传递的,所以在binarySearch函数里 sizeof(sortedArray) 返回的是指针的大小,不是数组的长度。正确的做法应该把数组的长度也当做一个参数传递到函数里,我已经修改过代码了,还在上面的在线运行代码里。