首页 文章

C：特定数组元素不会出现冒泡排序和二进制搜索

提问于
浏览 次
0

问题：进行二进制搜索时，只有中间元素始终正确 . 搜索时，其他元素提供空格而不是数字 . 图片：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; 
}
c++ arrays sorting search

1 回答

  • 1

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

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

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

    例如，按顺序排列8个元素的简单序列：

    1 2 3 4 5 6 7 8

    最初我们有一个长度为8个元素的序列 . 我们将选择8/2，即4作为中点，这给了我们这个（记住我们的索引是 zero-based ）：

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

    好 . 除非我们正在寻找的元素是 5 ，否则我们要么上涨，要么下跌 . 但有什么区别（除了显而易见的）？好吧，如果我们想要的东西大于 5 ，那么这就是我们要看的地方

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

    即保留一个 three 元素序列 . 但是，如果我们需要移动到低端（该值小于 5 ），那么我们将有以下左边来征服：

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

    即保留一个 four 元素序列 .

    要始终确保不跳过元素，请准确地保持以下内容：

    • 基本索引，仅在移动到更高分区时调整 .

    • 当前序列长度，使用每个分区进行调整 .

    • 当前序列中的中点计算 .

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

    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;
}

    祝你好运 .

    回复于

相关问题