看书时看到一个简洁的关于二分法的函数，有几个问题请教一下各位大神。

_HellAngel_

例题中给出的简单二分法函数是这个：

1. int binsearch(int x, int v[], int n)
   
2. {
   
3.     int low, high, mid;
   
4.    
   
5.     low = 0;
   
6.     high = n-1;
   
7.     while (low <= high){
   
8.         mid = (low+high) / 2;
   
9.         if(x < v[mid])
   
10.             high = mid - 1;
    
11.         else if(x > v[mid])
    
12.             low = mid + 1;
    
13.         else
    
14.             return mid;
    
15.     }
    
16.     return -1;
    
17. }

复制代码

然后有一个题目，说是让我简化一下这个函数，让它在循环里面只进行一次测试（原本的例题里进行了两次测试），让更多的测试在循环外进行。然后让我比较两个版本函数运行的时间。

我看了下答案，答案给出的是这个：

1. int binsearch(int x, int v[], int n)
   
2. {
   
3.     int low, high, mid;
   
4.    
   
5.     low = 0;
   
6.     high = n-1;
   
7.     mid = (low+high) / 2;
   
8.     while(low <= high && x!= v[mid]){
   
9.         if(x < v[mid])
   
10.              high = mid - 1;
    
11.         else
    
12.              low = mid + 1;
    
13.         mid = (low + high) / 2;
    
14.     }
    
15.     if(x == v[mid])
    
16.         return mid;
    
17.     else
    
18.         return -1;
    
19. }

复制代码

解答说，两种方案的执行时间几乎没有什么差异。





我想请教各位大神的问题是：
1、因为它只是个函数，我想知道如何能看出它的执行时间。
2、有没有更简单的方法，真的可以让执行时间变短。
谢谢各位大神看完小弟的帖子。

fallening_cu

mid = (low+high) / 2;//bug

_Rayx

回复 2# fallening_cu
说说。

   

fallening_cu

_Rayx 发表于 2012-11-11 19:02
回复 2# fallening_cu
说说。

1. #include <limits>
   
2. #include <iostream>
   
3. 
   
4. int main()
   
5. {
   
6.     int const a = std::numeric_limits<int>::max();
   
7.     int const b = std::numeric_limits<int>::max();
   
8. 
   
9.     std::cout << (a+b)/2 << std::endl;
   
10. 
    
11.     return 0;
    
12. }

复制代码

_Rayx

回复 4# fallening_cu

能传这么大的数组进去么。。。
   

x5miao

这不是效率的问题，而是第二个函数部分修正第一个的部分bug的问题

linux_c_py_php

没兴趣看, 不过送楼主一个标准库实现:

1. SYNOPSIS
   
2.        #include <stdlib.h>
   
3. 
   
4.        void *bsearch(const void *key, const void *base,
   
5.                      size_t nmemb, size_t size,
   
6.                      int (*compar)(const void *, const void *));

复制代码

fallening_cu

_Rayx 发表于 2012-11-11 20:37
回复 4# fallening_cu

能传这么大的数组进去么。。。

为什么不能？你算算 int arr[2^32] 才占了多大的地？
我台式机内存都 48G 了，更不要提超级计算机了

_Rayx

回复 8# fallening_cu


    48G。。。

NalaGinrut

fallening_cu 发表于 2012-11-11 20:59
为什么不能？你算算 int arr[2^32] 才占了多大的地？
我台式机内存都 48G 了，更不要提超级计算机了

你买的二手小型机吧