Implementing a binary search

This is a discussion on Implementing a binary search within the C++ Programming forums, part of the General Programming Boards category; Hi. Does anyone have any idea on how one would implement a binary search in C++? Any ideas will be ...

  1. #1
    diligentStudent()
    Join Date
    Apr 2002
    Posts
    79

    Implementing a binary search

    Hi. Does anyone have any idea on how one would implement a binary search in C++? Any ideas will be appreciated. I am designing a program that will read from a text file and has to be able to search for any character. I have the file I/O information, I need the code for the algorithm. Thanks.

  2. #2
    VA National Guard The Brain's Avatar
    Join Date
    May 2004
    Location
    Manassas, VA USA
    Posts
    903
    In order to use the binary search.. you must first sort your array.. in this example.. i used a bubble sort.. followed by a binary search.


    Code:
    
    #include<iostream>
    #include<cstdlib>
    using namespace std;
    
    int main()
    {
    
    system("cls");
    
    int array[11] = {90, 1, 43, 16, 32, 12, 6, 14, 96, 20, 3};
    
    cout << "\nHere is the unsorted array: \n\n";
    
    for(int i = 0; i < 11; i++)
    {
    	cout << " " << array[i] << "  ";
    }
    
    cout << endl << endl;
    system("pause");
    
    
    
    //Bubble Sort Algorithm
    for(int p = 0; p < 10; p++)			//The outter FOR loop will execute the
    {									//bubble sort "array capacity - 1" times.  
    	
    	int place_holder = 0;
    
    	for(int i = 0; i < 10; i++)			//The inner FOR loop executes an 
    	{									//"element by element" comparison
    		int j = i;						
    
    		if(array[i] > array[++j])		//The "swap" algorithm will "push"
    		{								//larger numbers to the greater 
    			place_holder = array[j];	//end of the array
    
    			array[j] = array[i];
    
    			array[i] = place_holder;
    		}
    		
    	}
    
    	if(place_holder == 0)			//A switch is provided to "break" the  
    									//FOR loop if no swaps are being made.
    		break;
    }
    
    
    cout << "\n\nHere is the sorted array: \n\n";
    
    for(int i = 0; i < 11; i++)
    {
    	cout << " " << array[i] << "  ";
    }
    
    cout << endl << endl;
    system("pause");
    
    int search_key = 0;
    cout << "\n\nEnter an integer type search key: ";
    cin >> search_key;
    
    
    
    
    //Binary Search 
    	
    	int low = 0;
    	int high = 10;	
    	int middle = 0;
    	
    	while( low <= high )
    	{
    		middle = ( low  + high ) / 2;
    		
    		if( search_key == array[middle] ) //match
    		{	
    			cout << "\nYour search key '" << search_key << "' was found in array element [" 
    				 << middle << "]\n\n"
    				 << "\nThank you for viewing my sort and search demonstration.";
    				 
    				 return EXIT_FAILURE;
    		}		
    		
    		else if( search_key < array[middle] )
    			
    			high = middle - 1;		//search low end of array
    		
    		else
    			
    			low = middle + 1;		//search high end of array
    	}
    
    	cout << "\nYour search key << search_key << is not part of the array.\n\n"
    		 << "Better luck next time.";
    
    return EXIT_SUCCESS;
    
    }
    Last edited by The Brain; 10-05-2004 at 07:01 PM.
    • "Problem Solving C++, The Object of Programming" -Walter Savitch
    • "Data Structures and Other Objects using C++" -Walter Savitch
    • "Assembly Language for Intel-Based Computers" -Kip Irvine
    • "Programming Windows, 5th edition" -Charles Petzold
    • "Visual C++ MFC Programming by Example" -John E. Swanke
    • "Network Programming Windows" -Jones/Ohlund
    • "Sams Teach Yourself Game Programming in 24 Hours" -Michael Morrison
    • "Mathmatics for 3D Game Programming & Computer Graphics" -Eric Lengyel

  3. #3
    diligentStudent()
    Join Date
    Apr 2002
    Posts
    79

    Looks Great

    Thanks Brain. I'll study the example you have posted. Much obliged.

  4. #4
    VA National Guard The Brain's Avatar
    Join Date
    May 2004
    Location
    Manassas, VA USA
    Posts
    903
    anytime
    • "Problem Solving C++, The Object of Programming" -Walter Savitch
    • "Data Structures and Other Objects using C++" -Walter Savitch
    • "Assembly Language for Intel-Based Computers" -Kip Irvine
    • "Programming Windows, 5th edition" -Charles Petzold
    • "Visual C++ MFC Programming by Example" -John E. Swanke
    • "Network Programming Windows" -Jones/Ohlund
    • "Sams Teach Yourself Game Programming in 24 Hours" -Michael Morrison
    • "Mathmatics for 3D Game Programming & Computer Graphics" -Eric Lengyel

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help with binary search.
    By StateofMind in forum C Programming
    Replies: 6
    Last Post: 05-06-2009, 03:14 PM
  2. searching and insertion in a binary search tree
    By galmca in forum C Programming
    Replies: 1
    Last Post: 03-26-2005, 05:15 PM
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 09:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21