25:
1014:, but this case can be attributed to any of the previous two (in order to simplify the code). Sooner or later the length of the segment will be a little less than a predetermined constant, and the process can be stopped.
1280:
628:
828:
690:
404:
293:
966:
1192:
1132:
448:
337:
1070:
1043:
576:
549:
486:
165:
366:
255:
225:
205:
185:
1012:
906:
867:
768:
729:
522:
1899:
35:
1810:
93:
50:
65:
830:, that the situation is similar to the previous, up to symmetry. Now, the required maximum can not be in the right side –
72:
1203:
1894:
79:
581:
1822:
61:
775:
637:
1816:
371:
260:
913:
1828:
1138:
1078:
409:
298:
1833:
123:
1863:
119:
86:
1048:
1021:
554:
527:
462:
141:
345:
234:
1819:(similar to ternary search, useful if evaluating f takes most of the time per iteration)
210:
190:
170:
971:
872:
833:
734:
695:
495:
1888:
1838:
127:
24:
1619:
To find the minimum, reverse the if/else statement or reverse the comparison.
731:. It means that the maximum further makes sense to look only in the interval
489:
42:
1843:
1775:# Left and right are the current bounds; the maximum is between them
692:, then the required maximum can not be located on the left side –
1825:(can be used to search for where the derivative changes in sign)
1616:"""Find maximum of unimodal function f() within .
207:. For the algorithm to be applicable, there must be some value
18:
1813:(can be used to search for where the derivative is zero)
1334:"""Left and right are the current bounds;
16:
Algorithm for finding the extrema of a unimodal function
46:
1206:
1141:
1081:
1051:
1024:
974:
916:
875:
836:
778:
737:
698:
640:
584:
557:
530:
498:
465:
412:
374:
348:
301:
263:
237:
213:
193:
173:
144:
167:
and that we know the maximum lies somewhere between
1274:
1186:
1126:
1064:
1037:
1006:
960:
900:
861:
822:
762:
723:
684:
622:
570:
543:
516:
480:
442:
398:
360:
331:
287:
249:
219:
199:
179:
159:
1275:{\displaystyle T(n)=T(2n/3)+1=\Theta (\log n)}
8:
51:introducing citations to additional sources
1844:N Dimensional Ternary Search Implementation
1234:
1205:
1176:
1146:
1140:
1116:
1086:
1080:
1056:
1050:
1029:
1023:
995:
982:
973:
968:, then the search should be conducted in
949:
927:
915:
889:
874:
844:
835:
811:
789:
777:
745:
736:
712:
697:
673:
651:
639:
608:
595:
583:
562:
556:
535:
529:
497:
464:
411:
373:
347:
300:
262:
236:
212:
192:
172:
143:
623:{\displaystyle l<m_{1}<m_{2}<r}
41:Relevant discussion may be found on the
1855:
138:Assume we are looking for a maximum of
630:. Then there are three possibilities:
7:
823:{\displaystyle f(m_{1})>f(m_{2})}
685:{\displaystyle f(m_{1})<f(m_{2})}
1900:Optimization algorithms and methods
1254:
399:{\displaystyle x\leq a<b\leq B}
288:{\displaystyle A\leq a<b\leq x}
14:
961:{\displaystyle f(m_{1})=f(m_{2})}
34:relies largely or entirely on a
23:
1811:Newton's method in optimization
1187:{\displaystyle m_{2}=r-(r-l)/3}
1127:{\displaystyle m_{1}=l+(r-l)/3}
1269:
1257:
1242:
1225:
1216:
1210:
1173:
1161:
1113:
1101:
1001:
975:
955:
942:
933:
920:
895:
876:
856:
837:
817:
804:
795:
782:
757:
738:
718:
699:
679:
666:
657:
644:
511:
499:
475:
469:
437:
431:
422:
416:
326:
320:
311:
305:
154:
148:
1:
1337:the maximum is between them.
443:{\displaystyle f(a)>f(b)}
332:{\displaystyle f(a)<f(b)}
492:function on some interval
1916:
1571:
1289:
116:ternary search algorithm
1823:Binary search algorithm
869:, so go to the segment
1276:
1188:
1128:
1066:
1039:
1008:
962:
902:
863:
824:
764:
725:
686:
624:
572:
545:
524:. Take any two points
518:
482:
444:
400:
362:
333:
289:
251:
221:
201:
181:
161:
1817:Golden-section search
1277:
1189:
1129:
1067:
1065:{\displaystyle m_{2}}
1040:
1038:{\displaystyle m_{1}}
1009:
963:
903:
864:
825:
765:
726:
687:
625:
573:
571:{\displaystyle m_{2}}
546:
544:{\displaystyle m_{1}}
519:
483:
445:
401:
363:
334:
290:
252:
222:
202:
182:
162:
1829:Interpolation search
1204:
1139:
1079:
1049:
1022:
972:
914:
873:
834:
776:
735:
696:
638:
582:
555:
528:
496:
481:{\displaystyle f(x)}
463:
410:
372:
346:
299:
261:
235:
211:
191:
171:
160:{\displaystyle f(x)}
142:
47:improve this article
1568:Iterative algorithm
1286:Recursive algorithm
361:{\displaystyle a,b}
250:{\displaystyle a,b}
1834:Exponential search
1649:absolute_precision
1622:"""
1601:absolute_precision
1559:absolute_precision
1520:absolute_precision
1367:absolute_precision
1340:"""
1319:absolute_precision
1272:
1184:
1124:
1062:
1035:
1004:
958:
898:
859:
820:
760:
721:
682:
620:
568:
541:
514:
478:
440:
396:
358:
329:
285:
247:
217:
197:
177:
157:
124:minimum or maximum
118:is a technique in
1895:Search algorithms
1868:cp-algorithms.com
578:in this segment:
220:{\displaystyle x}
200:{\displaystyle B}
180:{\displaystyle A}
112:
111:
97:
1907:
1879:
1878:
1876:
1874:
1864:"Ternary Search"
1860:
1800:
1797:
1794:
1791:
1788:
1785:
1782:
1779:
1776:
1773:
1770:
1767:
1764:
1761:
1758:
1755:
1752:
1749:
1746:
1743:
1740:
1737:
1734:
1731:
1728:
1725:
1722:
1719:
1716:
1713:
1710:
1707:
1704:
1701:
1698:
1695:
1692:
1689:
1686:
1683:
1680:
1677:
1674:
1671:
1668:
1665:
1662:
1659:
1656:
1653:
1650:
1647:
1644:
1641:
1638:
1635:
1632:
1629:
1626:
1623:
1620:
1617:
1614:
1611:
1608:
1605:
1602:
1599:
1596:
1593:
1590:
1587:
1584:
1581:
1578:
1575:
1563:
1560:
1557:
1554:
1551:
1548:
1545:
1542:
1539:
1536:
1533:
1530:
1527:
1524:
1521:
1518:
1515:
1512:
1509:
1506:
1503:
1500:
1497:
1494:
1491:
1488:
1485:
1482:
1479:
1476:
1473:
1470:
1467:
1464:
1461:
1458:
1455:
1452:
1449:
1446:
1443:
1440:
1437:
1434:
1431:
1428:
1425:
1422:
1419:
1416:
1413:
1410:
1407:
1404:
1401:
1398:
1395:
1392:
1389:
1386:
1383:
1380:
1377:
1374:
1371:
1368:
1365:
1362:
1359:
1356:
1353:
1350:
1347:
1344:
1341:
1338:
1335:
1332:
1329:
1326:
1323:
1320:
1317:
1314:
1311:
1308:
1305:
1302:
1299:
1296:
1293:
1281:
1279:
1278:
1273:
1238:
1193:
1191:
1190:
1185:
1180:
1151:
1150:
1133:
1131:
1130:
1125:
1120:
1091:
1090:
1071:
1069:
1068:
1063:
1061:
1060:
1044:
1042:
1041:
1036:
1034:
1033:
1013:
1011:
1010:
1007:{\displaystyle }
1005:
1000:
999:
987:
986:
967:
965:
964:
959:
954:
953:
932:
931:
907:
905:
904:
901:{\displaystyle }
899:
894:
893:
868:
866:
865:
862:{\displaystyle }
860:
849:
848:
829:
827:
826:
821:
816:
815:
794:
793:
769:
767:
766:
763:{\displaystyle }
761:
750:
749:
730:
728:
727:
724:{\displaystyle }
722:
717:
716:
691:
689:
688:
683:
678:
677:
656:
655:
629:
627:
626:
621:
613:
612:
600:
599:
577:
575:
574:
569:
567:
566:
550:
548:
547:
542:
540:
539:
523:
521:
520:
517:{\displaystyle }
515:
487:
485:
484:
479:
449:
447:
446:
441:
405:
403:
402:
397:
367:
365:
364:
359:
338:
336:
335:
330:
294:
292:
291:
286:
256:
254:
253:
248:
226:
224:
223:
218:
206:
204:
203:
198:
186:
184:
183:
178:
166:
164:
163:
158:
122:for finding the
120:computer science
107:
104:
98:
96:
62:"Ternary search"
55:
27:
19:
1915:
1914:
1910:
1909:
1908:
1906:
1905:
1904:
1885:
1884:
1883:
1882:
1872:
1870:
1862:
1861:
1857:
1852:
1807:
1802:
1801:
1798:
1795:
1792:
1789:
1786:
1783:
1780:
1777:
1774:
1771:
1768:
1765:
1762:
1759:
1756:
1753:
1750:
1747:
1744:
1741:
1738:
1735:
1732:
1729:
1726:
1723:
1720:
1717:
1714:
1711:
1708:
1705:
1702:
1699:
1696:
1693:
1690:
1687:
1684:
1681:
1678:
1675:
1672:
1669:
1666:
1663:
1660:
1657:
1654:
1651:
1648:
1645:
1642:
1639:
1636:
1633:
1630:
1627:
1624:
1621:
1618:
1615:
1612:
1609:
1606:
1603:
1600:
1597:
1594:
1591:
1588:
1585:
1582:
1579:
1576:
1573:
1570:
1565:
1564:
1561:
1558:
1555:
1552:
1549:
1546:
1543:
1540:
1537:
1534:
1531:
1528:
1525:
1522:
1519:
1516:
1513:
1510:
1507:
1504:
1501:
1498:
1495:
1492:
1489:
1486:
1483:
1480:
1477:
1474:
1471:
1468:
1465:
1462:
1459:
1456:
1453:
1450:
1447:
1444:
1441:
1438:
1435:
1432:
1429:
1426:
1423:
1420:
1417:
1414:
1411:
1408:
1405:
1402:
1399:
1396:
1393:
1390:
1387:
1384:
1381:
1378:
1375:
1372:
1369:
1366:
1363:
1360:
1357:
1354:
1351:
1348:
1345:
1342:
1339:
1336:
1333:
1330:
1327:
1324:
1321:
1318:
1315:
1312:
1309:
1306:
1303:
1300:
1297:
1294:
1291:
1288:
1202:
1201:
1142:
1137:
1136:
1082:
1077:
1076:
1052:
1047:
1046:
1025:
1020:
1019:
991:
978:
970:
969:
945:
923:
912:
911:
885:
871:
870:
840:
832:
831:
807:
785:
774:
773:
741:
733:
732:
708:
694:
693:
669:
647:
636:
635:
604:
591:
580:
579:
558:
553:
552:
531:
526:
525:
494:
493:
461:
460:
457:
408:
407:
370:
369:
344:
343:
297:
296:
259:
258:
233:
232:
209:
208:
189:
188:
169:
168:
140:
139:
136:
108:
102:
99:
56:
54:
40:
28:
17:
12:
11:
5:
1913:
1911:
1903:
1902:
1897:
1887:
1886:
1881:
1880:
1854:
1853:
1851:
1848:
1847:
1846:
1841:
1836:
1831:
1826:
1820:
1814:
1806:
1803:
1577:ternary_search
1572:
1569:
1566:
1535:ternary_search
1496:ternary_search
1295:ternary_search
1290:
1287:
1284:
1283:
1282:
1271:
1268:
1265:
1262:
1259:
1256:
1253:
1250:
1247:
1244:
1241:
1237:
1233:
1230:
1227:
1224:
1221:
1218:
1215:
1212:
1209:
1199:
1198:Run time order
1195:
1194:
1183:
1179:
1175:
1172:
1169:
1166:
1163:
1160:
1157:
1154:
1149:
1145:
1134:
1123:
1119:
1115:
1112:
1109:
1106:
1103:
1100:
1097:
1094:
1089:
1085:
1059:
1055:
1032:
1028:
1018:choice points
1016:
1015:
1003:
998:
994:
990:
985:
981:
977:
957:
952:
948:
944:
941:
938:
935:
930:
926:
922:
919:
908:
897:
892:
888:
884:
881:
878:
858:
855:
852:
847:
843:
839:
819:
814:
810:
806:
803:
800:
797:
792:
788:
784:
781:
770:
759:
756:
753:
748:
744:
740:
720:
715:
711:
707:
704:
701:
681:
676:
672:
668:
665:
662:
659:
654:
650:
646:
643:
619:
616:
611:
607:
603:
598:
594:
590:
587:
565:
561:
538:
534:
513:
510:
507:
504:
501:
477:
474:
471:
468:
456:
453:
452:
451:
439:
436:
433:
430:
427:
424:
421:
418:
415:
395:
392:
389:
386:
383:
380:
377:
357:
354:
351:
340:
328:
325:
322:
319:
316:
313:
310:
307:
304:
284:
281:
278:
275:
272:
269:
266:
246:
243:
240:
216:
196:
176:
156:
153:
150:
147:
135:
132:
110:
109:
45:. Please help
31:
29:
22:
15:
13:
10:
9:
6:
4:
3:
2:
1912:
1901:
1898:
1896:
1893:
1892:
1890:
1869:
1865:
1859:
1856:
1849:
1845:
1842:
1840:
1839:Linear search
1837:
1835:
1832:
1830:
1827:
1824:
1821:
1818:
1815:
1812:
1809:
1808:
1804:
1567:
1285:
1266:
1263:
1260:
1251:
1248:
1245:
1239:
1235:
1231:
1228:
1222:
1219:
1213:
1207:
1200:
1197:
1196:
1181:
1177:
1170:
1167:
1164:
1158:
1155:
1152:
1147:
1143:
1135:
1121:
1117:
1110:
1107:
1104:
1098:
1095:
1092:
1087:
1083:
1075:
1074:
1073:
1057:
1053:
1030:
1026:
996:
992:
988:
983:
979:
950:
946:
939:
936:
928:
924:
917:
909:
890:
886:
882:
879:
853:
850:
845:
841:
812:
808:
801:
798:
790:
786:
779:
771:
754:
751:
746:
742:
713:
709:
705:
702:
674:
670:
663:
660:
652:
648:
641:
633:
632:
631:
617:
614:
609:
605:
601:
596:
592:
588:
585:
563:
559:
536:
532:
508:
505:
502:
491:
472:
466:
454:
434:
428:
425:
419:
413:
393:
390:
387:
384:
381:
378:
375:
355:
352:
349:
341:
323:
317:
314:
308:
302:
282:
279:
276:
273:
270:
267:
264:
244:
241:
238:
230:
229:
228:
214:
194:
174:
151:
145:
133:
131:
129:
125:
121:
117:
106:
95:
92:
88:
85:
81:
78:
74:
71:
67:
64: –
63:
59:
58:Find sources:
52:
48:
44:
38:
37:
36:single source
32:This article
30:
26:
21:
20:
1871:. Retrieved
1867:
1858:
1017:
458:
137:
134:The function
115:
113:
100:
90:
83:
76:
69:
57:
33:
1772:right_third
1745:right_third
1688:right_third
1553:right_third
1487:right_third
1430:right_third
1889:Categories
1850:References
1757:left_third
1730:left_third
1655:left_third
1508:left_third
1472:left_third
1397:left_third
406:, we have
295:, we have
227:such that
130:function.
73:newspapers
1873:21 August
1264:
1255:Θ
1168:−
1159:−
1108:−
455:Algorithm
391:≤
379:≤
280:≤
268:≤
43:talk page
1805:See also
490:unimodal
342:for all
231:for all
128:unimodal
103:May 2007
87:scholar
1778:return
1532:return
1493:return
1373:return
89:
82:
75:
68:
60:
1790:right
1766:right
1703:right
1694:right
1670:right
1646:>=
1634:right
1625:while
1610:float
1607:->
1595:right
1514:right
1451:right
1418:right
1385:right
1352:right
1328:float
1325:->
1313:right
488:be a
368:with
339:, and
257:with
126:of a
94:JSTOR
80:books
1875:2023
1784:left
1760:else
1751:left
1736:<
1709:left
1676:left
1661:left
1640:left
1589:left
1547:left
1526:else
1478:<
1439:left
1412:left
1379:left
1364:<
1358:left
1307:left
1045:and
799:>
661:<
615:<
602:<
589:<
551:and
459:Let
426:>
385:<
315:<
274:<
187:and
66:news
1628:abs
1574:def
1346:abs
1292:def
1261:log
1072::
910:if
772:if
634:if
49:by
1891::
1866:.
1748:):
1721:if
1490:):
1463:if
1343:if
114:A
1877:.
1799:2
1796:/
1793:)
1787:+
1781:(
1769:=
1763::
1754:=
1742:(
1739:f
1733:)
1727:(
1724:f
1718:3
1715:/
1712:)
1706:-
1700:(
1697:-
1691:=
1685:3
1682:/
1679:)
1673:-
1667:(
1664:+
1658:=
1652::
1643:)
1637:-
1631:(
1613::
1604:)
1598:,
1592:,
1586:,
1583:f
1580:(
1562:)
1556:,
1550:,
1544:,
1541:f
1538:(
1529::
1523:)
1517:,
1511:,
1505:,
1502:f
1499:(
1484:(
1481:f
1475:)
1469:(
1466:f
1460:3
1457:/
1454:)
1448:*
1445:2
1442:+
1436:(
1433:=
1427:3
1424:/
1421:)
1415:+
1409:*
1406:2
1403:(
1400:=
1394:2
1391:/
1388:)
1382:+
1376:(
1370::
1361:)
1355:-
1349:(
1331::
1322:)
1316:,
1310:,
1304:,
1301:f
1298:(
1270:)
1267:n
1258:(
1252:=
1249:1
1246:+
1243:)
1240:3
1236:/
1232:n
1229:2
1226:(
1223:T
1220:=
1217:)
1214:n
1211:(
1208:T
1182:3
1178:/
1174:)
1171:l
1165:r
1162:(
1156:r
1153:=
1148:2
1144:m
1122:3
1118:/
1114:)
1111:l
1105:r
1102:(
1099:+
1096:l
1093:=
1088:1
1084:m
1058:2
1054:m
1031:1
1027:m
1002:]
997:2
993:m
989:;
984:1
980:m
976:[
956:)
951:2
947:m
943:(
940:f
937:=
934:)
929:1
925:m
921:(
918:f
896:]
891:2
887:m
883:;
880:l
877:[
857:]
854:r
851:;
846:2
842:m
838:[
818:)
813:2
809:m
805:(
802:f
796:)
791:1
787:m
783:(
780:f
758:]
755:r
752:;
747:1
743:m
739:[
719:]
714:1
710:m
706:;
703:l
700:[
680:)
675:2
671:m
667:(
664:f
658:)
653:1
649:m
645:(
642:f
618:r
610:2
606:m
597:1
593:m
586:l
564:2
560:m
537:1
533:m
512:]
509:r
506:;
503:l
500:[
476:)
473:x
470:(
467:f
450:.
438:)
435:b
432:(
429:f
423:)
420:a
417:(
414:f
394:B
388:b
382:a
376:x
356:b
353:,
350:a
327:)
324:b
321:(
318:f
312:)
309:a
306:(
303:f
283:x
277:b
271:a
265:A
245:b
242:,
239:a
215:x
195:B
175:A
155:)
152:x
149:(
146:f
105:)
101:(
91:·
84:·
77:·
70:·
53:.
39:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
