help with binary search

This is a discussion on help with binary search within the C++ Programming forums, part of the General Programming Boards category; Code: #include <iostream> using namespace std; int search(long array[], int size, long value); int main() { long nums[] = {5658845, ...

  1. #1
    Un Artiste Extraordinaire volk's Avatar
    Join Date
    Dec 2002
    Posts
    357

    help with binary search

    Code:
    #include <iostream>
    using namespace std;
    
    int search(long array[], int size, long value);
    
    int main()
    {
    	long nums[] = {5658845, 8080152, 1005231,
                       4520125, 4562555, 6545231,
                       7895122, 5552012, 3852085,
                       8777541, 5050552, 7576651,
                       8451277, 7825877, 7881200,
                       1302850, 1250255, 4581002};
    	
    	long number;
    	
    	int  results;
    
    	cout << "Enter a charge account number" << endl;
    	cin  >> number;
    
    	while (results = search(nums, 18, number) == -1)
    	{
    		cin.clear();
    		cin.ignore(INT_MAX, '\n');
    
    		cout << "Invalid entry" << endl;
    		cout << "Re-enter" << endl;
    		cin  >> number;
    	}
    
    	cout << "Your number is valid" << endl;
    
    	return 0;
    }
    
    int search(long array[], int size, long value)
    {
    	int first = 0;
    	int middle;
    	int last  = size - 1;
    
        int position = -1;
    	int found    = 0;
    
    	while (!found && first <= last)
    	{
    		middle = (first + last) / 2;
    
    		if (array[middle] == value)
    		{
    			found    = 1;
    			position = middle;
    		}
    
    		else if (array[middle] > value)
    			last  = middle - 1;
    
    		else
    			first = middle = 1;
    	}
    
    	return position;
    }
    For some reason, only 8777541, 4562555, and 3852085 are considered valid numbers. All of the other numbers are consider invalid or cause some kind of weird error.


    Never mind. I realize that the numbers have to be sorted in order for a binary search to work.
    Last edited by volk; 05-04-2003 at 03:08 PM.

  2. #2
    Un Artiste Extraordinaire volk's Avatar
    Join Date
    Dec 2002
    Posts
    357
    When I used a sorting algorithm, some numbers were still causing problems (like 7895122).

    Code:
    #include <iostream>
    using namespace std;
    
    int  search(long array[], int size, long value);
    
    void sort              (long array[], int size);
    
    int main()
    {
    	long nums[] = {5658845, 8080152, 1005231,
                       4520125, 4562555, 6545231,
                       7895122, 5552012, 3852085,
                       8777541, 5050552, 7576651,
                       8451277, 7825877, 7881200,
                       1302850, 1250255, 4581002};
    	long number;
    
    	int  results;
    
    	sort(nums, 18);
    
    	cout << "Enter a charge account number" << endl;
    	cin  >> number;
    
    	while ((results = search(nums, 18, number)) == -1)
    	{
    		cin.clear();
    		cin.ignore(INT_MAX, '\n');
    
    		cout << "Invalid entry" << endl;
    		cout << "Re-enter" << endl;
    		cin  >> number;
    	}
    
    		cout << "Your number is valid" << endl;
    
    	return 0;
    }
    
    int search(long array[], int size, long value)
    {
    	int first = 0;
    	int middle;
    	int last  = size - 1;
    
        int position = -1;
    	int found    = 0;
    
    	while (!found && first <= last)
    	{
    		middle = (first + last) / 2;
    
    		if (array[middle] == value)
    		{
    			found    = 1;
    			position = middle;
    		}
    
    		else if (array[middle] > value)
    			last  = middle - 1;
    
    		else
    			first = middle = 1;
    	}	
    
    	return position;
    }
    
    void sort(long array[], int size)
    {
    	long hold;
    	int  finish;
    
    	do
    	{
    		finish = 0;
    		
    		for (int i = 0; i < size - 1; i++)
    		{
    			if (array[i] > array[i + 1])
    			{
    				hold         = array[i];
    				array[i]     = array[i + 1];
    				array[i + 1] = hold;
    
    				finish = 1;
    			}
    		}
    	}while (finish != 0);
    }

  3. #3
    Un Artiste Extraordinaire volk's Avatar
    Join Date
    Dec 2002
    Posts
    357
    Could my compiler be a little faulty, or is there really something wrong with that code?

  4. #4
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    >>else
    >>first = middle = 1;
    A little typo in that one, eh?
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. searching and insertion in a binary search tree
    By galmca in forum C Programming
    Replies: 1
    Last Post: 03-26-2005, 04:15 PM
  2. deleting all nodes of a binary search tree...
    By sachitha in forum C++ Programming
    Replies: 3
    Last Post: 09-29-2004, 06:19 AM
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 08:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM

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