二进制搜索算法C++

Question

我想写一个函数，它需要一个整数数组&在给定值的第一个和最后一个之间搜索数组部分。如果该值在数组中，则返回该位置。如果不是，我想返回-1。

这里是我的功能代码。

int binarySearch(int *array, int min, int max, int value) { 
    int guess = 0; 
    bool found = false; 
    while (!found) { 
     guess = ((array[min] + array[max])/2); 
     if (array[guess] == value) { 
      found = true; 
      return guess; 
     } 
     else if (array[guess] < value) { 
      min = guess + 1; 
     } 
     else if (array[guess] > value) { 
      max = guess - 1; 
     } 
    } 
    return -1; 
} 

我不确定如何当你正在搜索的值不在数组中时跳出while循环吗？这是我为实现二进制搜索功能所遵循的伪代码：

1. 设min = 0和max = n-1（数组大小-1）。计算最大值和最小值的平均值，向下舍入（使其为整数）。
2. 如果array [guess]等于 target，则停止。你找到了！返回猜测。
3. 如果猜测是太 低，即，阵列[猜测] <目标，则设置最低=猜测+ 1
4. 否则，猜测是太高了。设置最大=猜测 - 1
5. 回到步骤2

Answer 1

我认为有必要改变函数的返回值。如果找到该项目，它应该返回一个有效的索引，否则返回guess，否则返回-1。

另外，您正在使用guess作为值和索引。这肯定会造成问题。

guess是下面的一个值。

guess = ((array[min] + array[max])/2); 

guess是下面的索引。

else if (array[guess] < value) { 

这里是我的建议：

// Return the index if found, -1 otherwise. 
int binarySearch(int *array, int first, int last, int value) 
{ 
    // Terminating condition 1. 
    // If first crosses last, the item was not found. 
    // Return -1. 
    if (first > last) 
    { 
     return -1; 
    } 

    int mid = (first + last)*0.5; 

    // Terminating condition 2. 
    // The item was found. Return the index. 
    if (array[mid] == value) 
    { 
     return mid; 
    } 

    // Recurse 
    if (array[mid] < value) 
    { 
     return binarySearch(array, mid+1, last, value); 
    } 
    else 
    { 
     return binarySearch(array, first, mid-1, value); 
    } 
} 

Answer 2

无需递归，如果你使用while循环，只记得每次来计算guess，并设置guess为索引的中间，不是他们的价值观：

int binarySearch (int *array, int first, int last, int value) 
{ 

    int guess = 0; 

    while (first != last || array[guess] == value) { 
     guess = (first + last)/2; 

     if (array[guess] == value) 
      return guess; 
     else if (array[guess] < value) 
      last = guess + 1; 
     else if (array[guess] > value) 
      first = guess - 1; 
    } 

    return -1; 
} 

我也建议

int first = 0, last = sizeof(array)/sizeof(array[0]) - 1; 

，而不是将它们作为参数。