对分查找

mingcxx

问题描述：实现对分查找使得在每次迭代中只有一个二路比较。
我不太明白“只有一个二路比较”是什么意思？难道是if else语句的分支判断吗？是说条件判断只能有两个分支的意思吗？
那下面这个传统的对分查找算法不是二路比较吗？

1. int binarySearch(const int A[], int N, int X)
   
2. {
   
3.     int low, high, mid;
   
4. 
   
5.     low = 0;high = N - 1;
   
6.     while (low <= high)
   
7.     {
   
8.         mid = (low + high) / 2;
   
9.         if (A[mid] < X)
   
10.             low = mid + 1;
    
11.         else if (A[mid] > X)
    
12.             high = mid - 1;
    
13.         else
    
14.             return mid;
    
15.     }
    
16.     return -1;        //not found
    
17. }

复制代码

这么写呢？是二路比较么？这个名词第一次听。

1. int binarySearch(const int A[], int N, int X)
   
2. {
   
3.         int low, high, mid;
   
4. 
   
5.         low = 0; high = N - 1;
   
6.         while (low < high)
   
7.         {
   
8.                 mid = (low + high) / 2;
   
9.                 if (A[mid] < X)
   
10.                         low = mid + 1;
    
11.                 else
    
12.                         high = mid;
    
13.         }
    
14.         if (A[low] == X)
    
15.                 return low;
    
16.         else
    
17.                 return -1;        //not found
    
18. }

复制代码

0洛枫0

学习

rayleigh_tong

看不懂，进来学习学习

安静的蓝

解决好的代码呢