Binary search

[aluhnev]

Hi all,have this code:

Hi all,have this code:
How do i implement binary search to display item.. found at index..
#include "stdafx.h"
#include<fstream>
#include<iostream>
#include<string>
#include<iomanip>
using namespace std;


struct sDetails{
    int kNum;
    string Name;
};


int _tmain(int argc, _TCHAR* argv[])
{

    sDetails students[5];

    ifstream infile;
    infile.open("student.txt");
    for (int i = 0; i < 5; i++)
    {
        infile >> students[i].kNum >> students[i].Name;


    }





    cout << "The Class List Is:\n";
    cout << "KNUM\t\tNAME\n";
    cout << endl;
    for (int i = 0; i < 5; i++)
    {
        cout << students[i].kNum << setw(15) << right <<  students[i].Name << endl;
    }






    infile.close();






    return 0;
}

[tinstaafl]

A binary search basically divides the collection in half, whichever half conatins the searched for item, that part is split in half again, and so on until only 1 item is left that equals the search term or the last 2 items that the search term falls between. A binary search can only be performed on a sorted collection.

Once you have some code, that shows a concerted effort, that you're having problems with, we'll be more than happy to help you.

[mike_2000_17]

First, I guess you are assuming that the student list in the input file is already is some sort of order (by number or by name). Otherwise, you have to sort the array first, because binary search requires an ordered array.

Second, we won't just give you code for your homework or exercise. You have to make the first steps, that is, show some attempt at solving the problem yourself.

As a starter, you should just look at the descriptions of the algorithm and try to write code that implements that strategy for your problem (which should be easy since most descriptions of the algorithm are already using C / C++ syntax!).

[aluhnev]

///This what i got so far,but it doesn't work.I have seen example if i had structure named;
/// but lost with the array. How to call in main.,anyway that's that i got now:

// student.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include<fstream>
#include<iostream>
#include<string>
#include<iomanip>
using namespace std;


struct sDetails{
    int kNum;
    string Name;

};
bool binarySearch(int student[], int size, int key);

int _tmain(int argc, _TCHAR* argv[])
{

    sDetails students[5];



    ifstream infile;
    infile.open("student.txt");
    for (int i = 0; i < 5; i++)
    {
        infile >> students[i].kNum >> students[i].Name;


    }





    cout << "The Class List Is:\n";
    cout << "KNUM\t\tNAME\n";
    cout << endl;
    for (int i = 0; i < 5; i++)
    {
        cout << students[i].kNum << setw(15) << right <<  students[i].Name << endl;
    }






    infile.close();
    cout << "\n\t\t\tEnter Key To Search: ";
    int key;
    cin >> key;


    // Passing Array, size and key To Search Key
        int result = binarySearch(students, 5, key);////// ?????????????

    if (result == 1)
        cout << "\n\t\t\tKey Found in Array " << endl;
    else
        cout << "\n\t\t\tKey NOT Found in Array " << endl;






    return 0;
}



bool binarySearch(int students[], int size, int key){
    int start = 1, end = size;
    int mid = (start + end) / 2;

    while (start <= end&& students[mid] != key){
        if (students[mid]<key){
            start = mid + 1;
        }
        else{
            end = mid - 1;
        }
        mid = (start + end) / 2;
    }// While Loop End

    if (students[mid] == key)
        return true; //Returnig to main
    else
        return false;//Returnig to main

    cout << "\n\n\n";
}// binarySearch Function Ends Here

[tinstaafl]

Just from a quick look, you're comparing an integer(key) to a struct object(students[mid]), which will never be equal. If kNum is the field you want to test for searching, then you need to specify that

while (start <= end && students[mid].kNum != key)

Just noticed the declaration is wrong too:

bool binarySearch(sDetails students[], int size, int key);