C++:特定的数组元素不会出现冒泡排序和二分查找

Question

+问题:进行二分查找时，只有中间元素始终正确。搜索其他元素时，会提供空格而不是数字。图片:http://i.imgur.com/7JOoCwk.png

赋值信息:编写一个程序，提示用户输入元素个数和数字本身被放置在一个整数数组中，该数组最多包含 50元素。然后程序应该提示用户输入一个整数使用二进制搜索在数组中搜索。确保包括以下内容沿途的步骤:

1) 必须在二进制搜索之前调用排序例程。您可以使用选择排序或冒泡排序。但是，必须实现排序在它自己的函数中而不是在 main 中。

2) 接下来包含一个由 main 调用的函数来实现二分查找。排序产生的有序数组应该传递给搜索返回查找值在排序数组中的位置的例程，如果值不在数组中，则为 -1。

3) 添加一个值返回函数来计算数据集的平均值。回想一下，平均值是数据值的总和除以数字的数据。你的程序应该输出数组的大小输入，用户输入的数组，排序后的数组，整数正在搜索的整数在排序数组(或适当的消息(如果它不在数组中)和数据集的平均值。

 #include<iostream>

    using namespace std;


    void bubbleSort(int [], int); 
    int searchBinary( int[], int, int); 
void displayArray(int[], int);

int main ()
{   
    int userValue;
    const int SIZE = 50;
    int numArray[SIZE];


    cout << "Enter the element numbers to be placed into the integer array." << endl;


    for (int count = 0; count < SIZE; count ++) 
    {

        cout << "enter integer #" << count + 1 << " "; 
        cin >> numArray[count]; 

        /*if (numArray[count] ==0)
            break; */

    }

    bubbleSort (numArray, SIZE); 
    cout << "The array has been sorted." << endl; 

    displayArray(numArray,SIZE); 


    cout << "what integer would you like to retrieve?";
    cin >> userValue; 

    cout << "Searching the array..." << endl; 
    cout << "The value you retrieved is ";
    cout << searchBinary(numArray, SIZE, userValue);

    return 0;
}


void bubbleSort (int arrayNumx[], int ELEMS)
    // bubbleSort function definition
{
    bool elemswap; 
int temp1 = 0; 
int endValue = ELEMS - 1; 

do
{
    elemswap = false;
    for (int count = 0; count < endValue; count ++)
    {       
        if (arrayNumx[count] > arrayNumx[count+1])
        {
            temp1 = arrayNumx[count];
    arrayNumx[count] = arrayNumx[count + 1];
    arrayNumx[count+1] = temp1; 
    elemswap = true;
    }
}
endValue--;
}
while (elemswap != false);
}


//searchBinary function header
int searchBinary (int intArray[], int totalElems, int quantity) 
    //searchBinary function definition
{
    int first = 0 ;
        int last = totalElems -1;
        int middle = 0; 
        int returnnum = -1;
        while (first <= last)
        {
            middle = (first + (last-first))/2;


            if (intArray[middle] == quantity)
                return middle; 


            else if (intArray[middle] < quantity)
                first = middle + 1; 



            else
                last = middle - 1;

        }

        return -1; 
}

void displayArray (int shownum[], int dec) 
{
    for(int count = 0; count < dec; count++)
        cout << shownum[count] << endl; 
}

Answer 1

二进制搜索中最常见的错误是忘记拆分的两边 长度不一定相同。 IE。当你计算这个时:

middle = (first + (last-first))/2;

然后使用middle作为比较元素，需要记住剩余分区的大小并不总是(last-first)/2。由于整数除法，分区的一侧可能比另一侧多一个元素。

例如8个元素依次排列的简单序列:

1 2 3 4 5 6 7 8

最初我们有一个长度为 8 个元素的序列。我们将选择 8/2，即 4，作为中点，这给了我们这个(记住我们的索引是从零开始):

1 2 3 4 5 6 7 8
------- X -----

好的。除非我们要查找的元素是 5，否则我们要么向上，要么向下。但是有什么区别(除了显而易见的)？好吧，如果我们想要的是大于 5，那么这就是我们要寻找的地方

1 2 3 4 5 6 7 8
          -----

即三 元素序列仍然存在。但是，如果我们需要移动到low 一侧(值小于 5)，那么我们将剩下以下内容需要征服:

1 2 3 4 5 6 7 8
-------

即一个四元素序列仍然存在。

要始终确保您不会跳过元素，请准确维护以下内容:

• 基本索引，只有在移动到更高的分区拆分时才会调整。
• 当前序列长度，随每个分区调整。
• 当前序列中的中点计算。

这是完成上述所有操作的一种方法。

size_t bin_search(int arr[], size_t len, int value)
{
    if (len < 1) // here for sanity sake
        return (size_t)-1;

    size_t base=0, mid=len/2;
    while (len > 1)
    {
        if (arr[base+mid] < value)
        {
            base += (mid+1); // relocate base
            len -= (mid+1);  // remaining length
        }
        else if (value < arr[base+mid])
        {
            // no change in base; length split
            len = mid; 
        }
        else return base+mid; // quick exit, found match

        // next midpoint length based on updated sequence length
        mid = len/2;
    }
    return (arr[base+mid] == value) ? base+mid : -1;
}

祝你好运。