מצחיק, דווקא ההבדל במקום הוא זניח ולא קשור לגודל של המערך, אבל דווקא היעילות תהיה נמוכה יותר (אם עוצרים מספיק מוקדם כמו שאמרתי, אז ההבדל יהיה בגלל שהחישובים על double וההמרות ל- int לוקחים יותר זמן מאשר עבודה על integers)

אז סגרנו על הפתרון עם הINT?

נגיד שבמערך יש 100 אברים. אתה מתחיל מהאיבר באינדקס 50 למרות שהאיבר האמצעי הוא 49. (אולי לא התכוונת, אבל בלי זה זה לא תמיד יפעל).

הקטע של ה- 1000 איטרציות - אצלך אתה ממשיך לחלק את המערך עד שהגודל שלו "שווה" 0 (כלומר עד שהוא מגיע למספר החיובי הכי קטן, מחלק אותו בשתיים ומקבל 0). מבדיקה שעשיתי, לוקח לו קצת יותר מ- 1000 פעמים לחלק את הקטע עד שהוא מגיע לאורך 0.

מצטער, אבל אני ממש לא מסכים איתך... כמה פעמים צריך לחלק מספר a ב-2 עד שהוא שנקבל מספר שקטן מ-1? התשובה פשוטה - (לוגריתם, בסיס 2, של a) ועוד 1 (מצטער על הנוסח, פשוט לא הצלחתי לסדר את זה אחרת בקלות). והסיבה פשוטה - כשתיקח את המספר הזה, שהוא תוצאת החלוקה, ותכפול אותו ב-2 n פעמים, כאשר n הוא מספר האיטרציות, תקבל לפחות מספר שגודלו 2 בחזקת n-1 . זאת אומרת שאם אתה צריך 1000 איטרציות, המספר ההתחלתי שלך (גודל המערך בסדר גודל) היה צריך להיות 2 בחזקת 999. מספר מאוד גדול, וממש לא נכנס ב-double מלכתחילה.

לגבי הסיבוכיות - התרכזתי בעיקר בפשטות של הקוד - readability - הסיבוכיות הממוצעת, כמו שאמר Icebreak (נדמה לי) גם ככה יותר טובה בחיפוש לינארי.

אני מסכים איתך לגמרי, אלא שבקוד שלך רצת כל עוד אורך הקטע גדול מ- 0, לא מ- 1:

while (currentArraySize > 0)
{
	currentArraySize /= 2;
	if (a[currentIndex] % 2 == 0)
		currentIndex += currentArraySize;
	else
		currentIndex -= currentArraySize;
}

צודק. שכחתי לעשות קאסט ל-int :

while ((int)currentArraySize > 0)