📄 page_666.html
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd"> <html> <head> <title>page_666</title> <link rel="stylesheet" href="reset.css" type="text/css" media="all"> <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /> </head> <body> <table summary="top nav" border="0" width="100%"> <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_665.html">< previous page</a></td> <td align="center" width="40%" style="background: #EEF3E2"><strong style="color: #2F4F4F; font-size: 120%;">page_666</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_667.html">next page ></a></td> </tr> <tr> <td align="left" colspan="3" style="background: #ffffff; padding: 20px;"> <table border="0" width="100%" cellpadding="0"><tr><td align="center"> <table border="0" cellpadding="2" cellspacing="0" width="100%"><tr><td align="left"></td> <td align="right"></td> </tr></table></td></tr><tr><td align="left"><p></p><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="right"><font face="Times New Roman, Times, Serif" size="2" color="#FF0000">Page 666</font></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 calculation</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="Courier New, Courier, Mono New, Courier, Mono" size="2">middle聽=聽(first聽+聽last)聽/聽2;</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">explains why the function precondition restricts the value of </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">length</font><font face="Times New Roman, Times, Serif" size="3"> to </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">INT_MAX/2</font><font face="Times New Roman, Times, Serif" size="3">. If the item being searched for happens to reside in the last position of the list (for example, when </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">item</font><font face="Times New Roman, Times, Serif" size="3"> equals 400 in our sample list), then </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">first + last</font><font face="Times New Roman, Times, Serif" size="3"> equals </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">length + length</font><font face="Times New Roman, Times, Serif" size="3">. If </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">length</font><font face="Times New Roman, Times, Serif" size="3"> is greater than </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">INT_MAX/2</font><font face="Times New Roman, Times, Serif" size="3">, the sum </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">length + length</font><font face="Times New Roman, Times, Serif" size="3"> would produce an integer overflow.</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">Notice in the table that whether we searched for 106, 400, or 406, the loop never executed more than four times. It never executes more than four times in a list of 11 components because the list is being cut in half each time through the loop. The table below compares a sequential search and a binary search in terms of the average number of iterations needed to find an item.</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="355" cellpadding="7"><tr><td valign="top"></td><td colspan="2" valign="middle"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2"><i>Average Number of Iterations</i></font></td></tr></table></td></tr><tr><td valign="middle"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="center"><font face="Times New Roman, Times, Serif" size="2"><i>Length of List</i></font></td></tr></table></td><td valign="middle"><font face="Times New Roman, Times, Serif" size="2"><i>Sequential Search</i></font></td><td valign="middle"><font face="Times New Roman, Times, Serif" size="2"><i>Binary Search</i></font></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"> 10</font></td></tr></table></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="right"><font face="Times New Roman, Times, Serif" size="2">5.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">2.9</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"> 100</font></td></tr></table></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="right"><font face="Times New Roman, Times, Serif" size="2">50.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">5.8</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"> 1,000</font></td></tr></table></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="right"><font face="Times New Roman, Times, Serif" size="2">500.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">9.0</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">10,000</font></td></tr></table></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="right"><font face="Times New Roman, Times, Serif" size="2">5000.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">12.4</font></td></tr></table></td></tr></table></td></tr></table><br /><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">If the binary search is so much faster, why not use it all the time? It certainly is faster in terms of the number of times through the loop, but more computations are performed within the binary search loop than in the other search algorithms. This means that if the number of components in the list is small (say, less than 20), the sequential search algorithms are faster because they do less work at each iteration. As the number of components in the list increases, the binary search algorithm becomes relatively more efficient. Remember, however, that the binary search requires the list to be sorted, and sorting itself takes time. Keep three factors in mind when you are deciding which search algorithm to use:</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">1. The length of the list to be searched</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">2. Whether or not the list already is ordered</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">3. The number of times the list is to be searched</font></td><td></td></tr><tr><td colspan="3"></td></tr><tr><td colspan="3" height="1"></td></tr></table></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_665.html">< previous page</a></td> <td align="center" width="40%" style="background: #EEF3E2"><strong style="color: #2F4F4F; font-size: 120%;">page_666</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_667.html">next page ></a></td> </tr> </table> </body> </html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -