נתון התרגיל, "חיפוש במערך" - http://he.wikibooks.org/wiki/Java/%...%9C%D7%99%D7%9D

עריכה: לא הצלחתי להעלות טוב את הפתרון, אך הכל רשום בלינק המצ"ב.

השאלות שלי:
האם ניתן לבנות מנגנון מהיר יותר שיבצע את אותה המשימה? האם אפשר לבנות מנגנון מהיר יותר לחיפוש במערך, כאשר יודעים כי המערך מסודר בסדר עולה או יורד?
אם אפשר, אז הסבר מפורט, תודה!

Bad Spellers Unite!

אם ידוע שהמערך הוא בסדר עולה/יורד, אפשר לממש חיפוש בינארי שפועל בסיבוכיות logn...

יכול להיות שיש עוד שיפורים, אבל כבר ברמת החיפוש של המספר
מה שהם עשו זה לעבור אחד אחד על האיברים, להשוות ולהפסיק את החיפוש במידה ונמצא
(סיבוכיות N)

במידה והמערך ממויין ניתן להשתמש בדבר שנקרא חיפוש בינארי.
החיפוש הבינארי הוא יעיל מבחינה משמעותית
(סיבוכיות logN)
מה זה בעצם?

הראיון הכללי הוא שמסתכלים על האיבר האמצעי במערך שגם הערך שלו צריך להיות ממוצע יחסית
אם המספר המבוקש גדול ממנו זה אומר שכל הצד השמאלי לא רלוונטי ונמשיך לחפש רק מימין או להפך.

נאמר שהמערך הממויין שלי הוא
22, 11, 9, 7, 6, 5, 4

המספר שאנו מחפשים הוא 5

נגדיר גבולות למערך ונשווה לאמצע המערך
יש לנו אינדקס אפס בגבול שמאל
ואינדקס שש בגבול ימין
בוא נמצא את האמצע
6 + 0 / 2 = 3
באינדקס 3 יש את הספרה 7
נבדוק האם היא גדולה או קטנה ממה שאנו מחפשים
שבע גדול מחמש אז אין לנו בכלל מה להסתכל על המספרים שמימין לשבע כי זה מערך ממויין והם בוודאות גדולים ממנו ולא שווים לו
נצמצם את הראייה שלנו
הגבול הימני יהפוך להיות 6 כי את השאר פסלנו
שוב נחפש אמצע בגבולות המוגדרים החדשים לחיפוש
(הגבול הימני אינדקס 2 והשמאלי 0)
נחשב את אמצע הטווח שאנו מסתכלים עליו עכשיו
0 + 2 / 2 = 1
האיבר באינדקס 1 הוא 5
נפסיק את החיפוש

מה יקרה במצב שהמספר לא קיים הגבולות יצטמצמו עד שהגבול הימני יהיה קטן מהשמאלי
כבר אין טווח לחפש בו, כל מה שקיים נפסל
לכן גם חושבים על מצב שהגענו לצמצום של הכל והמספר בוודאות לא נמצא.

לא הסברתי כל כך בבהירות אבל
הנה אלגוריתם כללי מויקיפדיה למערך בגודל
N
וחיפוש של המספר
X
במערך

הוספתי הערות, תנסה להבין
אם יש לך שאלות אתה מוזמן לשאול
בהצלחה!

קוד:

int BinarySearch(arr a,int x)
{
       // הגדרת גבולות חיפוש

       // תחילה הגבול השמאלי הוא אפס 
       int left = 0;
       // 
       int right = N - 1;
       // האמצע יחושב בהמשך
       int middle;

       // כל ישנו טווח לחיפוש ולא הגענו כבר למצב שהשמאלי עבר את הימני
       while (left <= right)
       {
           // נחשב את האמצע, ישנו עיגול כלפי מטה כי זה כולל התחשבות במצב שסכום הגבולות הוא אי זוגי
           middle = floor((left + right)/2);

           // אם האיבר האמצעי גדול מהמבוקש
           if (a[middle] > x)
               // צמצום ראייה, הגבול הימני הוא האמצע שגילינו שהוא גדול יותר, פחות אחד
               right = middle - 1;
           else
               // אם האמצע לא גדול יותר, נבדוק האם הוא קטן יותר
               if (a[middle] < x)
                  // צמצום ראייה, כעת נרצה להסתכל רק על החלק הימני, הגדול יותר, לכן הגבול השמאלי הוא האמצע שכבר בדקנו פלוס אחד
                   left = middle + 1;
               // אחרת - למעשה האיבר שבאמצע לא גדול ולא קטן מהמספר המבוקש אלא שווה לו!
               else
                   return a[middle];
       }

       // האיבר לא נמצא
       return -1;
}

אז בהנחה שהמספרים מסודרים לפי סדר עולה או יורד,

נניח יש 7 מספרים בין רנדומאלים 1-9 במערך, מסודרים בסדר עולה 1 3 5 5 7 9 9

המשתמש מכניס את המספר 5, ע"פ סיבוכיות logN, כפי שאמרת, (אגב רק הערב התחלתי לקרוא על סיבוכיות ועל חיפוש בינארי). אז ע"פ סיבוכיות logN, באינדקס 3 נמצא 5, אך אנחנו רוצים את הראשון ברשימה, ובמקרה שלנו יש שם פעמיים 5, אם כך, האם התוכנית תחדל? או האם היא תצטרך במקרה הזה לבדוק גם מימינה וגם משמאלה? כי באותו אופן במקום הספרה 7 היה יכול להיות עוד 5 או שכל המספרים שם היו יוצאים 5 (ברנדומאליות..)

אגב, התחלתי להסתכל על התוכנית שכתבת, ומס' שאלות לגבי כמה דברים:
מה זה:

קוד:

int BinarySearch(arr a,int x)

מאיפה הגיע המשתנה floor בתחילת התוכנית?

קוד:

 a[middle] 

מה בדיוק הוכפל שם? מה זה a?

זה כמה שאלות התחלתיות כדי להבין מה אני קורא שם, תודה!

אגב, אני חדש (יחסית) בתיכנות, משתדל ללמוד כמה שיותר, החלטתי להתחיל בג'אווה כי יש לי מעט היכרות מהתיכון, אודה לכם אם תפנו אותי לתרגילים בתחום (ואם מצורף תשובות אז עוד יותר טוב).

תודה.

Bad Spellers Unite!

מאוד פשוט:

ציטוט:

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

נבנה מערך עזר בגודל 100 [ ]B(מאופס בתור התחלה), נעבור על המערך המקורי(מ1 עד 100) (נניח שמו [ ]A), ובכל פעם מבצעים השמה [ B[ i ]=A[ i;
ברור שבניה כזו עולה O(n).
לאחר שבצענו את בניית העזר תשובה לשאלה האם מספר X קיים במערך עולה בדיוק פעולה אחת.
פשוט בודקים האם 0=?[ B[ X , אם כן, אזי המספר אינו קיים, אחרת המספר קיים..

*כמובן שאת מערך העזר אפשר לבנות עוד בשלב הבניה הרנדומלית.. (ואז חסכנו את עלות הבניה..)

הנה

קוד:

int[] arr = new int[100];
int[] b = new int [100]
for(int i=0; i<arr.length; i++){ 
        arr[i] = (int) (1 + Math.random()*100);
		b[arr[i]] = arr[i];
}

boolean find(int x){
	if (x<1 || x >100)
		return false;
	return (b[x]!=0;
}	

אם רוצים את הדרישה הזו("יודפס מספר התא בו הוא מופיע לראשונה"), לא שמתי לב בהתחלה, אז פשוט אפשר ע"י שדרוג פשוט לתמוך גם בשאלתה מטופשת זו)

הנה זה עומד בדרישות..

קוד:

int[] arr = new int[100];
int[] b = new int [100]
for(int i=0; i<arr.length; i++){ 
        arr[i] = (int) (1 + Math.random()*100);
		if (b[arr[i]]==0)
			b[arr[i]]=arr[i]+i;
}

find(int x){
	if (x<1 || x >100)
		System.out.println("No!");
	else
		System.out.println("yes"+b[x]-x);
}