| 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149 |
- #include <stdio.h>
- int binsearch(int x, int v[], int n);
- int binsearch2(int x, int v[], int n);
- int binsearch3(int x, int v[], int n);
- int binsearch4(int x, int v[], int n);
- int main()
- {
- int sorted_ary[] = {1,
- 2,
- 3,
- 4,
- 5,
- 6,
- 7,
- 8,
- 9,
- 10,
- 11,
- 74,
- 132,
- 132,
- 137,
- 210,
- 216,
- 227,
- 231,
- 311,
- 330,
- 367,
- 431,
- 436,
- 455,
- 496,
- 502,
- 519,
- 546,
- 552,
- 573,
- 579,
- 637,
- 683,
- 693,
- 703,
- 732,
- 739,
- 740,
- 792,
- 827,
- 892,
- 962,
- 1015,
- 1062,
- 1063,
- 1078,
- 1083,
- 1099,
- 1110,
- 1124,
- 1165,
- 1193,
- 1200,
- 1218,
- 1229,
- 1286,
- 1289,
- 1289,
- 1296,
- 1300,
- 1302,
- 1310,
- 1313,
- 1326,
- 1353,
- 1372,
- 1383,
- 1429,
- 1454,
- 1455,
- 1464,
- 1472,
- 1481,
- 1515,
- 1578,
- 1588,
- 1604,
- 1620,
- 1627,
- 1653,
- 1700,
- 1741,
- 1790,
- 1857,
- 1953,
- 1982,
- 2023,
- 2049,
- 2073,
- 2077,
- 2120,
- 2127,
- 2128,
- 2137,
- 2160,
- 2172,
- 2193,
- 2212,
- 2228,
- 2250,
- 2300,
- 2347,
- 2396,
- 2405,
- 2437,
- 2440,
- 2477,
- 2484,
- 2618,
- 2734,
- 2739,
- 2749,
- 2856,
- 2900,
- 2967,
- 2973,
- 2991,
- 3022,
- 3039,
- 3050,
- 3083,
- 3100,
- 3163,
- 3172,
- 3177,
- 3213,
- 3231,
- 3241,
- 3275,
- 3288,
- 3289,
- 3319,
- 3406,
- 3417,
- 3473,
- 3502,
- 3521,
- 3548,
- 3568,
- 3614,
- 3615,
- 3657,
- 3664,
- 3719,
- 3779,
- 3808,
- 3813,
- 3823,
- 3848,
- 3902,
- 3918,
- 3930,
- 3939,
- 3949,
- 3965,
- 3977,
- 4010,
- 4018,
- 4094,
- 4110,
- 4148,
- 4152,
- 4180,
- 4265,
- 4271,
- 4282,
- 4309,
- 4331,
- 4373,
- 4374,
- 4410,
- 4414,
- 4485,
- 4576,
- 4584,
- 4589,
- 4592,
- 4675,
- 4676,
- 4677,
- 4715,
- 4719,
- 4772,
- 4823,
- 4827,
- 4846,
- 4874,
- 4881,
- 4906,
- 4968,
- 4976,
- 5031,
- 5077,
- 5083,
- 5115,
- 5178,
- 5251,
- 5265,
- 5308,
- 5335,
- 5365,
- 5409,
- 5417,
- 5507,
- 5523,
- 5537,
- 5549,
- 5600,
- 5615,
- 5649,
- 5667,
- 5686,
- 5764,
- 5792,
- 5795,
- 5799,
- 5822,
- 5843,
- 5885,
- 5910,
- 5926,
- 6049,
- 6069,
- 6116,
- 6157,
- 6200,
- 6203,
- 6211,
- 6324,
- 6406,
- 6515,
- 6521,
- 6551,
- 6573,
- 6587,
- 6606,
- 6629,
- 6708,
- 6720,
- 6763,
- 6850,
- 6881,
- 6930,
- 6955,
- 6979,
- 7063,
- 7100,
- 7210,
- 7216,
- 7283,
- 7339,
- 7350,
- 7363,
- 7399,
- 7413,
- 7435,
- 7449,
- 7449,
- 7455,
- 7469,
- 7496,
- 7524,
- 7577,
- 7578,
- 7578,
- 7601,
- 7604,
- 7626,
- 7713,
- 7749,
- 7766,
- 7808,
- 7810,
- 7827,
- 7837,
- 7948,
- 7962,
- 7966,
- 7996,
- 8017,
- 8056,
- 8092,
- 8151,
- 8189,
- 8204,
- 8225,
- 8227,
- 8228,
- 8231,
- 8239,
- 8323,
- 8351,
- 8356,
- 8364,
- 8370,
- 8387,
- 8402,
- 8408,
- 8421,
- 8444,
- 8447,
- 8466,
- 8468,
- 8580,
- 8630,
- 8671,
- 8694,
- 8729,
- 8812,
- 8815,
- 8822,
- 8826,
- 8855,
- 8924,
- 8955,
- 9006,
- 9008,
- 9027,
- 9065,
- 9077,
- 9107,
- 9153,
- 9157,
- 9184,
- 9188,
- 9191,
- 9207,
- 9286,
- 9319,
- 9358,
- 9377,
- 9466,
- 9491,
- 9527,
- 9547,
- 9592,
- 9641,
- 9656,
- 9745,
- 9828,
- 9834,
- 9837,
- 9840,
- 9869,
- 9895,
- 9916,
- 9925,
- 9943,
- 9957,
- 9963,
- 10019,
- 10066,
- 10083,
- 10095,
- 10114,
- 10156,
- 10168,
- 10259,
- 10276,
- 10428,
- 10435,
- 10461,
- 10509,
- 10540,
- 10578,
- 10597,
- 10624,
- 10647,
- 10664,
- 10757,
- 10762,
- 10785,
- 10797,
- 10803,
- 10813,
- 10822,
- 10844,
- 10847,
- 10859,
- 10910,
- 10990,
- 11065,
- 11091,
- 11119,
- 11125,
- 11313,
- 11315,
- 11534,
- 11622,
- 11633,
- 11677,
- 11730,
- 11757,
- 11801,
- 11809,
- 11931,
- 11965,
- 11965,
- 11994,
- 11996,
- 11998,
- 12097,
- 12098,
- 12133,
- 12146,
- 12160,
- 12209,
- 12215,
- 12289,
- 12338,
- 12354,
- 12382,
- 12391,
- 12395,
- 12409,
- 12441,
- 12478,
- 12489,
- 12497,
- 12507,
- 12520,
- 12544,
- 12549,
- 12608,
- 12741,
- 12790,
- 12896,
- 12901,
- 13084,
- 13094,
- 13115,
- 13115,
- 13157,
- 13206,
- 13269,
- 13316,
- 13375,
- 13393,
- 13435,
- 13435,
- 13440,
- 13454,
- 13504,
- 13512,
- 13537,
- 13583,
- 13590,
- 13616,
- 13621,
- 13632,
- 13638,
- 13668,
- 13732,
- 13787,
- 13826,
- 13831,
- 13848,
- 13855,
- 13881,
- 13885,
- 13918,
- 13971,
- 13988,
- 14025,
- 14031,
- 14107,
- 14179,
- 14190,
- 14195,
- 14259,
- 14315,
- 14321,
- 14350,
- 14396,
- 14401,
- 14410,
- 14417,
- 14425,
- 14450,
- 14451,
- 14537,
- 14654,
- 14655,
- 14658,
- 14786,
- 14800,
- 14808,
- 14826,
- 14876,
- 14888,
- 14925,
- 14956,
- 14960,
- 14996,
- 15063,
- 15102,
- 15110,
- 15150,
- 15163,
- 15165,
- 15170,
- 15173,
- 15176,
- 15210,
- 15211,
- 15212,
- 15341,
- 15347,
- 15370,
- 15419,
- 15421,
- 15465,
- 15508,
- 15525,
- 15684,
- 15701,
- 15740,
- 15774,
- 15780,
- 15825,
- 15840,
- 15845,
- 15881,
- 15883,
- 15886,
- 15904,
- 15925,
- 15992,
- 16013,
- 16071,
- 16071,
- 16112,
- 16132,
- 16141,
- 16163,
- 16188,
- 16255,
- 16282,
- 16412,
- 16419,
- 16423,
- 16426,
- 16474,
- 16509,
- 16522,
- 16573,
- 16592,
- 16596,
- 16627,
- 16649,
- 16708,
- 16717,
- 16745,
- 16767,
- 16792,
- 16844,
- 16859,
- 16889,
- 16889,
- 16903,
- 16917,
- 16942,
- 17023,
- 17036,
- 17069,
- 17080,
- 17140,
- 17246,
- 17302,
- 17346,
- 17357,
- 17409,
- 17420,
- 17421,
- 17454,
- 17464,
- 17512,
- 17617,
- 17673,
- 17767,
- 17808,
- 17847,
- 17875,
- 17899,
- 17925,
- 17952,
- 17972,
- 18055,
- 18083,
- 18102,
- 18105,
- 18169,
- 18240,
- 18243,
- 18244,
- 18250,
- 18334,
- 18365,
- 18371,
- 18399,
- 18452,
- 18494,
- 18498,
- 18504,
- 18539,
- 18559,
- 18624,
- 18716,
- 18783,
- 18871,
- 18872,
- 18888,
- 18889,
- 18893,
- 18901,
- 18959,
- 18987,
- 19017,
- 19039,
- 19070,
- 19102,
- 19141,
- 19146,
- 19158,
- 19185,
- 19220,
- 19243,
- 19267,
- 19338,
- 19351,
- 19373,
- 19493,
- 19744,
- 19754,
- 19764,
- 19772,
- 19827,
- 19834,
- 19880,
- 19894,
- 19939,
- 19963,
- 19971,
- 20034,
- 20048,
- 20050,
- 20050,
- 20116,
- 20197,
- 20210,
- 20227,
- 20245,
- 20285,
- 20308,
- 20323,
- 20363,
- 20381,
- 20531,
- 20571,
- 20595,
- 20675,
- 20695,
- 20700,
- 20728,
- 20759,
- 20782,
- 20789,
- 20817,
- 20837,
- 20869,
- 20912,
- 20919,
- 20943,
- 21046,
- 21050,
- 21075,
- 21076,
- 21119,
- 21129,
- 21136,
- 21156,
- 21181,
- 21203,
- 21206,
- 21223,
- 21281,
- 21345,
- 21354,
- 21375,
- 21411,
- 21456,
- 21489,
- 21615,
- 21642,
- 21674,
- 21724,
- 21726,
- 21729,
- 21733,
- 21736,
- 21748,
- 21836,
- 21896,
- 21937,
- 21965,
- 21984,
- 21999,
- 22027,
- 22050,
- 22054,
- 22125,
- 22161,
- 22176,
- 22216,
- 22306,
- 22323,
- 22350,
- 22365,
- 22367,
- 22376,
- 22383,
- 22396,
- 22412,
- 22424,
- 22448,
- 22451,
- 22516,
- 22535,
- 22561,
- 22596,
- 22637,
- 22688,
- 22703,
- 22713,
- 22771,
- 22820,
- 22874,
- 22894,
- 22925,
- 22933,
- 22962,
- 22963,
- 22972,
- 23010,
- 23016,
- 23258,
- 23274,
- 23360,
- 23367,
- 23384,
- 23430,
- 23446,
- 23480,
- 23571,
- 23703,
- 23703,
- 23735,
- 23761,
- 23805,
- 23887,
- 23950,
- 24009,
- 24088,
- 24097,
- 24107,
- 24132,
- 24143,
- 24176,
- 24207,
- 24226,
- 24255,
- 24274,
- 24363,
- 24386,
- 24389,
- 24392,
- 24394,
- 24410,
- 24478,
- 24496,
- 24567,
- 24578,
- 24635,
- 24636,
- 24658,
- 24703,
- 24705,
- 24739,
- 24883,
- 24909,
- 24916,
- 24938,
- 24976,
- 24978,
- 24987,
- 25031,
- 25142,
- 25144,
- 25227,
- 25312,
- 25316,
- 25344,
- 25351,
- 25376,
- 25489,
- 25502,
- 25502,
- 25509,
- 25559,
- 25656,
- 25680,
- 25697,
- 25720,
- 25789,
- 25898,
- 25921,
- 25926,
- 25999,
- 26006,
- 26025,
- 26045,
- 26052,
- 26158,
- 26162,
- 26195,
- 26266,
- 26304,
- 26371,
- 26373,
- 26455,
- 26456,
- 26474,
- 26544,
- 26614,
- 26637,
- 26647,
- 26685,
- 26686,
- 26706,
- 26712,
- 26716,
- 26722,
- 26824,
- 26867,
- 26895,
- 26986,
- 27009,
- 27016,
- 27016,
- 27059,
- 27078,
- 27110,
- 27124,
- 27157,
- 27168,
- 27181,
- 27192,
- 27213,
- 27286,
- 27306,
- 27308,
- 27401,
- 27465,
- 27522,
- 27575,
- 27642,
- 27665,
- 27670,
- 27722,
- 27760,
- 27795,
- 27801,
- 27827,
- 27849,
- 27870,
- 27877,
- 27883,
- 27891,
- 27984,
- 27993,
- 28025,
- 28075,
- 28108,
- 28118,
- 28124,
- 28132,
- 28139,
- 28149,
- 28219,
- 28317,
- 28320,
- 28342,
- 28375,
- 28443,
- 28476,
- 28490,
- 28492,
- 28506,
- 28536,
- 28578,
- 28591,
- 28602,
- 28660,
- 28661,
- 28685,
- 28780,
- 28808,
- 28820,
- 28897,
- 28947,
- 29024,
- 29032,
- 29073,
- 29095,
- 29118,
- 29204,
- 29224,
- 29233,
- 29246,
- 29348,
- 29369,
- 29380,
- 29449,
- 29479,
- 29503,
- 29510,
- 29570,
- 29658,
- 29662,
- 29665,
- 29675,
- 29677,
- 29718,
- 29719,
- 29813,
- 29849,
- 29859,
- 29869,
- 29908,
- 29963,
- 29973,
- 30007,
- 30011,
- 30050,
- 30066,
- 30067,
- 30107,
- 30175,
- 30203,
- 30206,
- 30230,
- 30232,
- 30270,
- 30292,
- 30346,
- 30372,
- 30406,
- 30407,
- 30416,
- 30435,
- 30451,
- 30486,
- 30522,
- 30532,
- 30557,
- 30586,
- 30589,
- 30627,
- 30642,
- 30718,
- 30732,
- 30748,
- 30791,
- 30809,
- 30845,
- 30875,
- 30890,
- 30893,
- 30906,
- 30939,
- 30941,
- 30954,
- 31000,
- 31009,
- 31040,
- 31044,
- 31047,
- 31054,
- 31077,
- 31090,
- 31149,
- 31160,
- 31214,
- 31227,
- 31264,
- 31269,
- 31362,
- 31459,
- 31488,
- 31490,
- 31508,
- 31619,
- 31629,
- 31715,
- 31805,
- 31815,
- 31816,
- 31817,
- 31842,
- 31912};
-
- //{
- //}
- // for (int i =0; i < 1011; i++)
- // printf("%d\n",sorted_ary[i]);
- for (int i =0; i < 10000; i++)
- {
- int k = binsearch4(i,sorted_ary,1011);
- printf("returns: %d \n",k);
- }
-
- return(0);
- }
- /* binsearch: find x in v[0] <= v[1] <= ... <= v[n-1] */
- int binsearch(int x, int v[], int n)
- {
- int low, high, mid;
- low = 0;
- high = n - 1;
- while (low < high) {
- mid = (low+high)/2;
- if (x < v[mid])
- high = mid;
- else if (x > v[mid])
- if (low!=mid)
- low = mid;
- else
- {
- if (x == v[high])
- return high;
- return -1;
- }
- else /* found match */
- return mid;
- }
- return -1; /* no match */
- }
- /* binsearch: find x in v[0] <= v[1] <= ... <= v[n-1] */
- int binsearch2(int x, int v[], int n)
- {
- int low, high, mid;
- low = 0;
- high = n - 1;
- while (low < high)
- {
- mid = (low+high)/2;
- if (x < v[mid])
- high = mid;
- else
- {
- if (x == v[mid])
- return mid;
- if (low != mid)
- low = mid;
- else
- {
- if (x == v[high])
- return high;
- if (x == v[low])
- return low;
- return -1;
- }
- }
- }
- return -1;
- }
- int binsearch3(int x, int v[], int n)
- {
- int low, high, mid;
- low = 0;
- high = n - 1;
- while (low < high)
- {
- mid = (low+high)/2;
- if (x < v[mid])
- {
- if (mid != high)
- high = mid;
- else
- break;
- }
- else
- {
- if (x == v[mid])
- break;
- else if (low != mid)
- low = mid;
- else
- break;
- }
- }
- if (x == v[high])
- return high;
- if (x == v[mid])
- return mid;
- if (x == v[low])
- return low;
- return -1;
- }
- int binsearch4(int x, int v[], int n)
- {
- int low, high, mid;
- low = 0;
- high = n-1;
- mid = (low+high)/2;
-
- while ((low < high) && (x != v[mid]) && (mid != high) && (low != mid))
- {
- if (x < v[mid])
- high=mid;
- else
- low=mid;
- mid = (low+high)/2;
- }
-
- if (x == v[high])
- return high;
- if (x == v[mid])
- return mid;
- if (x == v[low])
- return low;
- return -1;
- }
|
