searching_in_infinite_array.cpp

#include<iostream>

using namespace std;

int binarySearch(int arr[], int toFind, int low, int high)
{
    int mid = (low + high) / 2;
    while (low <= high)
    {
        if (arr[mid] == toFind)
        {
            return mid;
        }
        else if (arr[mid] > toFind)
        {
            high = mid - 1;
            mid = (low + high) / 2;
        }
        else
        {
            low = mid + 1;
            mid = (low + high) / 2;
        }
    }
    return -1;
}

int main(){
    int sizeOfArray;
    cin >> sizeOfArray;
    int arr[sizeOfArray];
    for (int i = 0; i < sizeOfArray; i++)
    {
        cin >> arr[i];
    }
    int toFind;
    cin >> toFind;
    if(arr[0] == toFind){
        cout<<0;
        return 0;
    }
    int i = 1;
    while(arr[i] < toFind){
        i *= 2;
    }
    if(arr[i] == toFind){
        cout<<i;
        return 0;
    }
    cout<<binarySearch(arr, toFind, i/2-1, i-1);
}

// 500
// 5 12 17 20 21 24 31 33 36 39 41 46 47 51 57 58 59 61 63 72 83 88 99 103 109 110 111 119 120 122 125 126 134 137 140 141 143 147 149 150 157 159 164 166 171 180 188 201 207 209 217 223 229 239 243 244 245 246 247 251 252 254 255 261 262 264 265 267 268 270 271 274 278 285 290 293 295 301 314 321 323 325 328 337 348 350 378 379 387 390 393 401 403 407 409 410 412 414 415 416 423 426 427 429 431 434 442 443 448 450 458 463 465 471 475 476 483 485 488 489 495 499 500 501 506 507 511 512 518 526 529 533 540 544 559 565 567 578 588 589 596 600 605 607 609 612 615 617 618 619 624 625 629 633 637 642 662 664 671 672 676 680 682 684 685 686 690 699 704 705 709 717 718 725 727 729 732 740 741 744 746 747 748 752 757 761 762 765 768 772 775 777 781 782 786 789 798 802 808 809 812 815 816 820 826 832 835 844 850 851 856 860 862 864 873 877 882 883 884 894 895 896 897 898 899 904 907 910 918 925 928 929 931 935 937 943 952 958 959 961 963 969 970 973 977 993 994 995 998 1002 1008 1012 1013 1024 1026 1028 1030 1031 1035 1048 1052 1053 1055 1056 1057 1058 1060 1062 1063 1072 1073 1077 1085 1092 1093 1094 1095 1097 1098 1104 1111 1119 1125 1126 1134 1141 1142 1143 1145 1146 1147 1154 1156 1157 1166 1175 1181 1199 1202 1206 1214 1219 1222 1224 1226 1227 1228 1229 1232 1234 1243 1245 1246 1256 1257 1261 1262 1267 1273 1274 1275 1278 1281 1282 1283 1284 1292 1293 1294 1299 1301 1303 1304 1311 1314 1315 1318 1320 1321 1325 1329 1340 1345 1349 1359 1361 1363 1376 1380 1384 1385 1386 1389 1391 1392 1394 1397 1399 1404 1408 1410 1412 1426 1427 1429 1431 1441 1444 1447 1456 1463 1465 1467 1468 1471 1475 1477 1481 1487 1490 1492 1493 1495 1497 1498 1500 1505 1515 1516 1523 1529 1530 1536 1537 1541 1550 1552 1562 1568 1571 1576 1580 1583 1598 1601 1604 1605 1611 1617 1620 1624 1632 1633 1643 1645 1646 1648 1649 1655 1665 1671 1678 1693 1694 1700 1705 1706 1707 1716 1717 1719 1721 1724 1725 1726 1734 1739 1742 1744 1757 1763 1773 1775 1777 1778 1784 1787 1795 1796 1797 1803 1815 1817 1818 1819 1823 1831 1837 1842 1848 1850 1854 1857 1859 1860 1864 1865 1870 1873 1878 1880 1885 1888 1891 1892 1894 1900 1906 1909 1911 1915 1923 1928 1929 1930 1932 1935 1941 1945 1946 1947 1948 1961 1962 1963 1974 1975 1983 1989 1995
// 21