fork(94) download
copy 
  1.  
  2. // This code is in C++11
  3.  
  4. #include <iostream>
  5. #include <algorithm>
  6. #include <functional>
  7. #include <memory>
  8. #include <climits>
  9. #include <iterator>
  10.  
  11. using namespace std;
  12.  
  13. // :), generic functor
  14. template <typename ArgType, typename ResultType>
  15. struct PredUniqueElements : public std::unary_function<ArgType, ResultType> {
  16.  
  17. public:
  18.     PredUniqueElements(ArgType ref) : prev(ref) {}
  19.  
  20.    ResultType operator() (ArgType curr) {
  21.       ArgType old = prev;
  22.       prev = curr;
  23.       return curr != old;
  24.    }
  25.  
  26. private:
  27.     ArgType prev;
  28. };
  29.  
  30. int GenerateDataSet(int A[], int size) {
  31.     for(int i = 0; i < size; i++)
  32.         A[i] = rand()%size;
  33.  
  34.     sort(A, A+size);
  35.  
  36.     // predicate funtor definition
  37.     PredUniqueElements<int, bool> pred(INT_MIN);
  38.  
  39.     // Retain only unique elements
  40.     auto it = copy_if (A, A+size, A, pred);
  41.     return distance(A, it);
  42. }
  43.  
  44. // Returns location of key, or -1 if not found
  45. int BinarySearchSimple(int A[], int l, int r, int key, int &count)
  46. {
  47.     int m;
  48.  
  49.     while( l <= r )
  50.     {
  51.         m = l + (r-l)/2;
  52.  
  53.         count++;
  54.         if( A[m] == key ) // first comparison
  55.             return m;
  56.  
  57.         count++;
  58.         if( A[m] < key ) // second comparison
  59.             l = m + 1;
  60.         else
  61.             r = m - 1;
  62.     }
  63.  
  64.     return -1;
  65. }
  66.  
  67. int BinarySearch(int A[], int l, int r, int key, int &count)
  68. {
  69.     int m;
  70.  
  71.     while( r - l > 1 )
  72.     {
  73.         m = l + (r-l)/2;
  74.  
  75.         count++;
  76.         if( A[m] <= key )
  77.             l = m;
  78.         else
  79.             r = m;
  80.     }
  81.  
  82.     count++;
  83.     if( A[l] == key )
  84.         return l;
  85.     else
  86.         return -1;
  87. }
  88.  
  89. void TestCase_01() {
  90.     int size = 2048;
  91.     auto_ptr<int> buf(new int[size]);
  92.     int *A = buf.get();
  93.  
  94.     size = GenerateDataSet(A, size);
  95.  
  96.     copy(A, A+size, ostream_iterator<int>(cout, " ")), cout << endl;
  97.  
  98.     int key = 193;
  99.     int count;
  100.  
  101.     // We are only interested in comparison count
  102.     count = 0;
  103.     BinarySearchSimple(A, 0, size-1, key, count);
  104.     cout << "BinarySearchSimple " << count << endl;
  105.  
  106.     count = 0;
  107.     BinarySearch(A, 0, size-1, key, count);
  108.     cout << "BinarySearch " << count << endl;
  109. }
  110.  
  111. int main() {
  112.     srand(unsigned(time(NULL)));
  113.  
  114.     TestCase_01();
  115.  
  116.     return 0;
  117. }
  118.  
Success #stdin #stdout 0s 3032KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 2 3 5 6 7 8 10 11 14 15 16 18 19 21 24 25 29 30 31 32 33 35 37 40 41 42 46 48 51 52 53 55 57 62 63 65 66 68 70 71 75 76 77 79 80 83 84 85 86 90 92 97 98 99 100 101 102 104 105 107 109 110 111 113 114 116 117 120 121 122 123 125 126 127 129 131 134 136 137 138 139 140 141 142 143 144 146 150 151 154 155 157 158 159 162 163 164 165 166 167 169 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 188 189 190 191 192 193 194 195 197 199 200 201 202 204 205 206 207 208 211 214 216 218 219 221 222 223 224 225 226 227 229 230 231 233 235 237 239 240 244 245 247 249 250 252 254 255 257 258 260 261 262 263 264 266 267 268 269 270 271 273 274 276 277 278 279 282 283 284 288 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 307 308 310 311 312 314 315 316 317 318 320 321 322 323 324 327 329 330 332 334 335 336 337 338 340 344 345 348 349 351 353 355 356 358 359 360 363 364 365 367 370 371 372 373 374 375 376 377 378 380 381 382 384 387 388 392 393 394 398 400 401 402 403 405 406 408 410 412 414 415 417 418 419 420 421 422 423 424 425 426 429 431 432 433 437 438 439 443 445 446 447 450 451 456 458 460 461 463 464 465 467 470 471 472 473 474 475 478 479 480 481 483 484 485 486 488 489 492 493 495 496 497 498 499 500 501 502 504 506 507 509 511 515 516 517 518 519 520 521 522 523 526 531 533 534 535 541 542 543 544 545 546 549 550 551 553 554 555 561 562 563 564 565 571 572 574 575 577 578 579 581 583 584 586 591 592 594 596 597 599 600 603 604 605 606 608 609 610 612 614 615 616 618 621 623 624 625 626 627 629 630 632 635 638 639 640 641 643 644 645 646 648 649 651 654 655 656 658 660 664 665 667 670 671 672 673 675 677 679 680 681 682 684 685 688 689 690 691 693 697 700 702 703 705 706 707 708 709 710 712 714 719 720 721 723 725 728 730 731 732 734 738 739 742 743 744 745 746 748 749 750 753 754 755 757 759 761 762 763 764 765 768 769 770 771 772 773 774 775 776 778 779 780 781 785 787 788 789 790 791 793 794 795 796 797 798 799 800 802 803 804 805 807 809 811 813 814 815 816 818 819 820 821 822 823 824 826 828 829 830 831 835 839 840 841 843 845 846 848 853 854 855 856 857 858 859 860 861 862 863 865 866 868 869 870 873 875 876 878 881 882 883 886 889 893 894 895 898 899 900 901 902 903 904 905 909 910 912 913 914 915 916 917 918 919 921 922 924 926 927 930 932 933 935 938 939 940 942 948 949 951 952 954 956 960 962 963 964 965 966 968 969 970 971 974 976 978 979 980 982 984 985 986 987 988 991 992 995 996 997 998 1002 1003 1004 1005 1008 1010 1011 1016 1017 1018 1019 1020 1021 1023 1024 1028 1031 1032 1033 1034 1035 1037 1039 1041 1042 1043 1046 1047 1048 1049 1051 1052 1053 1054 1055 1059 1060 1063 1065 1067 1069 1070 1071 1072 1073 1074 1077 1079 1080 1081 1082 1084 1085 1087 1091 1093 1096 1099 1100 1101 1102 1104 1105 1107 1108 1111 1112 1116 1117 1120 1122 1123 1124 1125 1126 1127 1128 1131 1132 1136 1138 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1152 1153 1154 1155 1159 1160 1161 1162 1164 1165 1167 1168 1174 1176 1178 1180 1181 1182 1184 1186 1188 1189 1190 1191 1193 1195 1197 1198 1200 1201 1202 1204 1205 1206 1207 1211 1216 1218 1219 1220 1221 1223 1224 1225 1226 1227 1231 1232 1233 1234 1237 1238 1239 1240 1241 1243 1244 1246 1247 1248 1249 1251 1253 1254 1256 1257 1258 1259 1260 1261 1263 1264 1265 1266 1267 1269 1270 1271 1274 1275 1276 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1294 1295 1297 1301 1302 1303 1304 1305 1306 1308 1311 1313 1314 1315 1318 1320 1321 1323 1324 1326 1327 1330 1332 1333 1334 1335 1337 1338 1339 1340 1341 1342 1343 1345 1347 1348 1349 1350 1352 1355 1358 1359 1360 1362 1363 1364 1368 1370 1371 1372 1373 1374 1375 1378 1381 1382 1385 1387 1388 1390 1391 1394 1396 1397 1398 1400 1401 1402 1403 1404 1405 1406 1410 1411 1412 1415 1416 1417 1419 1420 1421 1422 1424 1425 1426 1427 1428 1429 1430 1431 1433 1435 1437 1438 1439 1440 1441 1442 1443 1444 1445 1448 1450 1451 1452 1453 1458 1462 1466 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476 1477 1478 1479 1480 1481 1482 1484 1485 1486 1487 1490 1491 1492 1493 1494 1495 1497 1499 1502 1506 1507 1513 1514 1515 1516 1518 1519 1521 1524 1525 1528 1529 1531 1532 1533 1535 1536 1537 1541 1542 1543 1545 1546 1547 1548 1549 1551 1552 1553 1554 1555 1556 1557 1558 1561 1562 1563 1564 1565 1567 1569 1571 1573 1574 1576 1578 1580 1582 1583 1584 1585 1588 1589 1590 1591 1592 1594 1595 1596 1597 1600 1601 1603 1605 1606 1609 1611 1612 1614 1615 1617 1618 1621 1622 1624 1625 1627 1628 1629 1632 1633 1634 1635 1636 1637 1638 1640 1641 1644 1646 1647 1648 1649 1650 1652 1655 1657 1658 1660 1663 1665 1666 1667 1668 1669 1670 1672 1673 1676 1677 1679 1681 1682 1683 1684 1685 1686 1692 1693 1694 1695 1696 1698 1699 1703 1704 1707 1709 1710 1711 1712 1713 1715 1716 1719 1720 1721 1722 1723 1724 1725 1726 1727 1728 1729 1730 1732 1733 1734 1735 1737 1738 1739 1740 1741 1742 1743 1744 1748 1752 1753 1756 1757 1758 1762 1764 1765 1768 1770 1771 1772 1773 1774 1775 1777 1778 1780 1781 1783 1784 1786 1787 1788 1789 1790 1791 1792 1793 1795 1796 1797 1798 1800 1801 1803 1805 1809 1810 1811 1813 1814 1815 1816 1819 1820 1821 1822 1823 1824 1826 1828 1829 1830 1831 1832 1833 1835 1837 1838 1839 1840 1841 1844 1846 1847 1848 1849 1851 1852 1856 1857 1859 1860 1861 1862 1863 1865 1866 1867 1868 1871 1873 1875 1876 1877 1878 1880 1881 1882 1883 1884 1885 1886 1887 1888 1889 1890 1891 1895 1899 1900 1901 1902 1903 1904 1905 1907 1910 1915 1918 1920 1921 1923 1927 1928 1932 1934 1935 1937 1938 1940 1941 1942 1943 1946 1947 1948 1950 1951 1952 1953 1954 1955 1958 1960 1964 1965 1969 1970 1971 1972 1974 1975 1978 1979 1981 1982 1983 1986 1988 1990 1991 1992 1993 1995 1997 1998 1999 2001 2002 2003 2004 2009 2010 2011 2012 2016 2020 2022 2027 2028 2029 2030 2031 2032 2034 2035 2039 2040 2041 2043 2046 
BinarySearchSimple 17
BinarySearch 11
https://ideone.com/76bad0
language:
C++14 (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!