C++

Forum

 
Binary Search Only Returns First and Last Elements

maenielwolf (10)
Hello, I am trying to finish this assignment and cannot seem to figure out what is wrong and multiple web searches and textbook reviews have been of no help.

I have an array with 10 number stored in it and am trying to do a linear search and a binary search on the array for a given number. The linear search is working correctly for all ten numbers. The binary search is only returning the first and last numbers element locations and returns a -1 for all element locations between. I would appreciate anyone who can give the code a once over and direct me where I am going wrong?

I have not been able to find any issues with my binarSearch function but I have displayed my sortArray to ensure that it is working properly and it appears to be so I have to assume I am overlooking some error in my binarySearch function or I have an improper call somewhere in main. Any and all help is appreciated. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
 


int main() {
	char choice;

	do {
		// Lotto numbers array
		int lotto[SIZE] = { 13579, 62483, 26791, 77777, 26792, 79422, 33445, 85647, 55555, 93121 };
		// Holds user input for winning number
		int winNum;


		cout << "\nWhat was this week's winning number?" << endl;
		cin >> winNum;

		// Searches array for winning nummber using a linear and binary searches
		int linResult = linearSearch(lotto, SIZE, winNum);
		int binResult = binarySearch(lotto, SIZE, winNum);

		// Determines if winNum was found 
		if (linResult == -1 && binResult == -1)

			cout << "\nSorry the number " << winNum << " was not a winner this week" << endl;
		// If winning number was found display info
		else {

			cout << "\nCongrats " << winNum << " was a winner! " << "Your winning number was \n"
				<< "found using a linear search at element " << linResult 
				<< " and a binary search at element " << binResult << "\n" << endl;

			// Call array sort and display array passing lotto and SIZE
			cout << "Here are the numbers entered into the unsorted array"<< endl;
					showArray(lotto, SIZE);
			cout << "\nSorting array now..." << endl;
				
					sortArray(lotto, SIZE);
					selectionSort(lotto, SIZE);
								
			cout << "\nHere are the sorted numbers in the array" << endl;
			
					showArray(lotto, SIZE);

		}

		// Repeat program?
		cout << "\nWould you like to enter another number? Y/N?" << endl;
		cin >> choice;
	} while (choice == 'Y' || choice == 'y');



	return 0;

}

// Binary search of array elements for winning number
int binarySearch(int array[], int size, int searchBin) {

	int first = 0,
		last = size - 1,
		middle,
		position = -1;
	bool found = false;

	while (!found && first <= last) {

		middle = ((first + last) / 2);
		if (array[middle] == searchBin) {
			found = true;
			position = middle;
		}
		else if (array[middle] > searchBin)
			last = middle - 1;
		else
			first = middle + 1;
	}
	return position;
}
// Display array elements after sorting
void showArray(int array[], int size) {

	for (int count = 0; count < size; count++)
		cout << array[count] << " " << endl;
}
Last edited on
TheIdeasMan (6817)
Hi,

The data must be sorted to do a binary search :+)
maenielwolf (10)
I have a both bubble sort and a selection sort in my code. Am I calling the binarySearch wrong in main?
TheIdeasMan (6817)
Yes, binary search is called before any sort function.
maenielwolf (10)
Ok so I need to do something like what i have below to fix my wrong element issue but since I want to display the unsorted and the sorted code at the end, is there a way of returning the array back to original form? If that makes sense?


// Searches array for winning number using a linear and binary searches
int linResult = linearSearch(lotto, SIZE, winNum);

sortArray(lotto, SIZE);
selectionSort(lotto, SIZE);

int binResult = binarySearch(lotto, SIZE, winNum);

// Determines if winNum was found
if (linResult == -1 && binResult == -1)
TheIdeasMan (6817)
For demonstration purposes you could have multiple copies of the original data.

There is no point in calling the sort routines one after the other.
maenielwolf (10)
Ok thanks for the help I knew it was probably something small but could not figure it out. I only have a bubble and selection sort for practice using both versions.
Topic archived. No new replies allowed.