page_664.html

Programming and Problem Solving with C++

</tr><tr><td colspan="3"></td>
</tr><tr><td colspan="3" height="1"></td>
</tr></table><table border="0" cellspacing="0" cellpadding="0"><tr><td rowspan="5"></td>
  <td colspan="3" height="12"></td>
  <td rowspan="5"></td>
</tr><tr><td colspan="3"></td>
</tr><tr><td></td>
  <td><font face="Times New Roman, Times, Serif" size="3">In the third iteration (Figure 12-7c), </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">middle</font><font face="Times New Roman, Times, Serif" size="3"> and </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">first</font><font face="Times New Roman, Times, Serif" size="3"> are both 0. The value 24 is compared with 12, the value in </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">list[middle]</font><font face="Times New Roman, Times, Serif" size="3">. Because 24 is greater than 12, </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">first</font><font face="Times New Roman, Times, Serif" size="3"> becomes </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">middle+1</font><font face="Times New Roman, Times, Serif" size="3">. In the fourth iteration (Figure 12-7d), </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">first</font><font face="Times New Roman, Times, Serif" size="3">, </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">last</font><font face="Times New Roman, Times, Serif" size="3">, and </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">middle</font><font face="Times New Roman, Times, Serif" size="3"> are all the same. Again, 24 is compared with the value in </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">list[middle]</font><font face="Times New Roman, Times, Serif" size="3">. Here 24 is less than 64, so </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">last</font><font face="Times New Roman, Times, Serif" size="3"> becomes </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">middle-1</font><font face="Times New Roman, Times, Serif" size="3">. Now that </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">last</font><font face="Times New Roman, Times, Serif" size="3"> is less than </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">first</font><font face="Times New Roman, Times, Serif" size="3">, the process stops; found is </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">FALSE</font><font face="Times New Roman, Times, Serif" size="3">.</font></td>
<td></td>
</tr><tr><td colspan="3"></td>
</tr><tr><td colspan="3" height="1"></td>
</tr></table><table border="0" cellspacing="0" cellpadding="0"><tr><td rowspan="5"></td>
  <td colspan="3" height="12"></td>
  <td rowspan="5"></td>
</tr><tr><td colspan="3"></td>
</tr><tr><td></td>
  <td><font face="Times New Roman, Times, Serif" size="3">The binary search algorithm is the most complex algorithm that we have examined so far. The table below shows </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">first</font><font face="Times New Roman, Times, Serif" size="3">, </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">last</font><font face="Times New Roman, Times, Serif" size="3">, </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">middle</font><font face="Times New Roman, Times, Serif" size="3">, and </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">list[middle]</font><font face="Times New Roman, Times, Serif" size="3"> for searches of 106, 400, and 406, using the same data as in the previous example. Go over the results shown in this table carefully.</font></td>
<td></td>
</tr><tr><td colspan="3"></td>
</tr><tr><td colspan="3" height="1"></td>
</tr></table><table cellpadding="0" cellspacing="0" border="0" width="100%"><tr><td height="12"></td></tr><tr><td>
<table cellspacing="0" width="521" cellpadding="7"><tr><td valign="bottom"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Courier New, Courier, Mono New, Courier, Mono" size="2"><i>item</i></font></td></tr></table></td><td valign="bottom"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Courier New, Courier, Mono New, Courier, Mono" size="2"><i>first</i></font></td></tr></table></td><td valign="bottom"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Courier New, Courier, Mono New, Courier, Mono" size="2"><i>last</i></font></td></tr></table></td><td valign="bottom"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Courier New, Courier, Mono New, Courier, Mono" size="2"><i>middle</i></font></td></tr></table></td><td valign="bottom"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Courier New, Courier, Mono New, Courier, Mono" size="2"><i>list[middle]</i></font></td></tr></table></td><td valign="bottom"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2"><i>Termination of Loop</i></font></td></tr></table></td></tr><tr><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2">106</font></td></tr></table></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2"> 0</font></td></tr></table></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2">10</font></td></tr></table></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2"> 5</font></td></tr></table></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2">103</font></td></tr></table></td><td valign="top"></td></tr><tr><td valign="top"></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2"> 6</font></td></tr></table></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2">10</font></td></tr></table></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2"> 8</font></td></tr></table></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2">200</font></td></tr></table></td><td valign="top"></td></tr><tr><td valign="top"></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2"> 6</font></td></tr></table></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2"> 7</font></td></tr></table></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2"> 6</font></td></tr></table></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2">106</font></td></tr></table></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="right"><font face="Courier New, Courier, Mono New, Courier, Mono" size="2">found = TRUE</font></td></tr></table></td></tr><tr><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2">400</font></td></tr></table></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2"> 0</font></td></tr></table></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2">10</font></td></tr></table></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2"> 5</font></td></tr></table></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2">103</font></td></tr></table></td><td valign="top"></td></tr><tr><td valign="top"></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2"> 6</font></td></tr></table></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2">10</font></td></tr></table></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2"> 8</font></td></tr></table></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2">200</font></td></tr></table></td><td valign="top"></td></tr><tr><td valign="top"></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2"> 9</font></td></tr></table></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2">10</font></td></tr></table></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2"> 9</font></td></tr></table></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2">300</font></td></tr></table></td><td valign="top"></td></tr><tr><td valign="top"></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2">10</font></td></tr></table></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2">10</font></td></tr></table></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2">10</font></td></tr></table></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2">400</font></td></tr></table></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="right"><font face="Courier New, Courier, Mono New, Courier, Mono" size="2">found = TRUE</font></td></tr></table></td></tr><tr><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2">406</font></td></tr></table></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2"> 0</font></td></tr></table></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2">10</font></td></tr></table></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2"> 5</font></td></tr></table></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2">103</font></td></tr></table></td><td valign="top"></td></tr><tr><td valign="top"></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2"> 6</font></td></tr></table></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2">10</font></td></tr></table></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2"> 8</font></td></tr></table></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2">200</font></td></tr></table></td><td valign="top"></td></tr><tr><td valign="top"></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2"> 9</font></td></tr></table></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2">10</font></td></tr></table></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2"> 9</font></td></tr></table></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2">300</font></td></tr></table></td><td valign="top"></td></tr><tr><td valign="top"></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2">10</font></td></tr></table></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2">10</font></td></tr></table></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2">10</font></td></tr></table></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2">400</font></td></tr></table></td><td valign="top"></td></tr><tr><td valign="top"></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2">11</font></td></tr></table></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2">10</font></td></tr></table></td><td valign="top"></td><td valign="top"></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="right"><font face="Courier New, Courier, Mono New, Courier, Mono" size="2">last &lt; first<br />
found = FALSE</font></td></tr></table></td></tr></table></td></tr></table><br />







</td>
</tr></table><p><font size="0"></font></p>
聽




  </td>
			</tr>
	
			<tr>
				<td align="left" width="30%" style="background: #EEF3E2"><a style="color: blue; font-size: 120%; font-weight: bold; text-decoration: none; font-family: verdana;" href="page_663.html">&lt;&nbsp;previous page</a></td>
				<td align="center" width="40%" style="background: #EEF3E2"><strong style="color: #2F4F4F; font-size: 120%;">page_664</strong></td>
				<td align="right" width="30%" style="background: #EEF3E2"><a style="color: blue; font-size: 120%; font-weight: bold; text-decoration: none; font-family: verdana;" href="page_665.html">next page&nbsp;&gt;</a></td>
			</tr>
		</table>
		</body>
	</html>