מבקש ליעל את הפונקציה (C++) בעזרת חיפוש בינארי

[Boomerang]

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

[Ghosthunter]

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

[bla7]

נגיד שבמערך יש 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 (נדמה לי) גם ככה יותר טובה בחיפוש לינארי.

[Boomerang]

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

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

[bla7]

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

while ((int)currentArraySize > 0)