Back to Code List
c++

Binary Search

A simple example of reading input from a file, performing a binary search, and outputting to a file.

   main.cpp

#include<iostream>
#include<fstream>
#include<string>
using namespace std;

const int ARRAY_SIZE = 100;

void input(int A[], int & n, const string & fileName) 
{
	ifstream inputFile;
	int value;

	inputFile.open(fileName.c_str());

	//read data until the end of the file
	while(inputFile >> value)
	{
		A[n] = value;
		n++;
	}

	inputFile.close();
}

void output(int A[], const int n, const string & fileName) 
{
	ofstream outputFile;
	outputFile.open(fileName.c_str());
	for (int i = 0; i < n; i++)
	  	 outputFile << A[i] << "  "; 
	 
	outputFile.close();
}

//If the search value x is in the array, then return the index of x in the array; otherwise return -1. first is the first index and last is the last index of the portion of the array you want to search for x; x is the number you want to search in the array
int binarySearch(int array[], int first, int last, int x)
{
	int position;
    // start at middle
    position = (first + last) / 2;
    while((array[position] != x) && (first <= last))
    {
        if (array[position] > x)               // If the number is > key, ..
            last = position - 1;    
        else                                                
            first = position + 1;     
        position = (first + last) / 2;
    }
    return position;
}

int main()
{
	int A[ARRAY_SIZE], B[ARRAY_SIZE], C[ARRAY_SIZE];// array C is used to hold the search results temporarily
	int n = 0;// the number of elements stored in A
	int m = 0;// the number of elements stored in B
	string dataFile = "hw1_Q6_data.txt"; // the name of the data file 
	string searchFile = "hw1_Q6_search.txt"; // the name of the search file 
	string outputFile = "hw1_Q6_output.txt"; // the name of the output file 

	input(A, n, dataFile); 
	input(B, m, searchFile); 

	for (int i = 0; i < m; i++)
	{
		C[i] = binarySearch(A, 0, n-1, B[i]); 
		//cout << "The position of " << B[i] << " is " << C[i] << endl; 
	}

	output(C, m, outputFile);

	cout << endl; 
	
	return 0;
}    

   data.txt

13 17 24 39 52 54 69 71 74 75 78 84 87 90 91 127 132 136 147 155 159 170 179 182 184 186 186 189 191 197     

   search.txt

35 147 259 197 65 13 69 31 87 170 78 191 179 64 186     

   output.txt

2  18  29  29  5  0  6  2  12  21  10  28  22  5  26