Hi, below is my code for binary search algorithm.

My question is, what if I enter more than 1 same numbers in the array? How should i modify my code to print out all the locations where that same number is found?

For example,
if I entered the number 2 at three different locations,
let's say, array[3], array[6] and array[17],
how should I ask my compiler to return all the three locations instead of one?

P.S. the below code returns only 1 position even if the number is entered multiple times.

Thanks in Advance :)

// Binary Search Algorithm ... Conceptual code

#include<iostream>
using namespace std;

int main()
{
    cout<<"--- Binary Search Algorithm ---"<<endl;

    cout<<endl<<endl;

    int size;
    cout<<"How many numbers you want to enter: ";
    cin>>size;

    cout<<endl<<endl;

    int array[size];

    cout<<"Enter "<<size<<" numbers one by one: "<<endl;

    for(int i=0; i<size; i++)
    {
        cout<<"Enter the number ["<<(i+1)<<"] : ";
        cin>>array[i];
    }

    cout<<endl<<endl;

    int find;
    cout<<"Which number you want to find in array: ";
    cin>>find;

    cout<<endl<<endl;

    // -----------------------   Binary Search Algorithm

    int first = 0;
    int last = size - 1; 
    int middle = ((first + last) / 2);

    while(first <= last)
    {
        if(array[middle] < find)
        {
            first = (middle + 1);
        }
        else if(array[middle] == find)
        {
            cout<<"The number "<<find<<" is found at position "<<(middle+1);
            cout<<endl;
            break;
            // (middle + 1) bcz array starts at 0 index
        }
        else
        {
            last = (middle - 1);
        }

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

    }

    cout<<endl<<endl;

    if(first > last)
    {
        cout<<"The number "<<find<<" is not found."<<endl;
    }

    cout<<endl<<endl;

    // The End

    return 0;

}

Recommended Answers

All 4 Replies

A binary tree stores data in sorted order (if you traverse the tree as left-middle-right). As such there is no reason to have the same value stored in more than one location. If you need to store the frequency then add that as a value in each node. If ylolu need to store more than the frequency and the value you can make node.Value the pointer to another list that contains one node for each repetition. as in

Node
    Pointer left      pointer to left sub-tree
    pointer right     poin  ter to rightsub-tree
    pointer reps      pointer to first instance of this value

Okay ThankYou all.
yes i did search on google, but with different keywords.
Reverend Jim, I get it. actually i accidently entered a number twice, it was on locations 2 and 8, the compiler showed me the 8th location, while according to my code, i guess the number is searched in 1st half, then goes to middle location or second hal, so 2nd postion was in the 1st half, but the compiler ignored it and returned 8th position.

If your code added a number that was already in the tree then your code has a bug. A while back I posted some code snippets on sorting. One of the implementations was a binary tree. The code is vbscript and is posted here.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.