C++

Forum

 
need help with binary search

beginner123 (220)
i need to search through a file using 3 different binary searches and i need to use a compraision count on each search to count how many times it take to find the correct number in the file. I got the first one working but when i search using the second one the result is always 0 so the count isnt working the the search isnt working. and when i run the last one it says midpoint is being used without initialized
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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
 
void BinarySearch (ItemType& item, bool& found)
{
	int midPoint;
	int first = 0;
	int last = list.length-1;
	bool  moreToSearch = first <= last;
	found = false;

	int Count = 0;

	while (moreToSearch && !found)
	{
		 midPoint = (first + last) / 2;
  
	if (item.number < list.info[midPoint].number)
	{
		Count +=1;
		 last = midPoint - 1;
		 moreToSearch = first <= last;
	}
	else if (item.number > list.info[midPoint].number) 
	{
		Count+=2;
		first = midPoint +1;
		moreToSearch = first <= last;
	}
	 else 
	{ 
		Count +=2;
		item = list.info[midPoint];
		found = true;
	}
 } 
	cout << "number of Binary counts : " << Count << endl;
}

int ForgetfulBinarySearch(ItemType& item, bool& found)
{
	int first = 0;
	int last = list.length-1;
	int midpoint;
		found = false;

	int Count = 0;

	while (first < last)
	{
		midpoint = (first + last)/2;
		
		if(item.number > list.info[midpoint].number)
		{
			Count +=1;
			first = midpoint+1;
		}
		else
		{
			last = midpoint;
		}
	}
	if (last == -1)
	{
		Count +=2;
		return -1;
	}
	else if (item.number == list.info[first].number)
	{
		Count +=2;
		found = true;
		return first;
	}
	else 
		return-1;

	cout << "number of Forgetful Binary counts : " << Count << endl;
}

int REBinarySearch (ItemType& item, bool& found)

{
	int first = 0;
	int last = list.length -1;
	int midpoint;
	found = false;
	int Count = 0;
	while (first <= last)
	{
		(midpoint + last) / 2;
		if ( item.number == list.info[midpoint].number)
	{
		found = true;
		return midpoint;
	}
		else if (item.number > list.info[midpoint].number)
			first = midpoint + 1;
		else
			last = midpoint - 1;
	}
	return -1;
}
beginner123 (220)
anyone?
Topic archived. No new replies allowed.