אלגוריתמים ב- Javascript - הסביר חיפוש בינארי

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

מה עושה הקורס?

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

אתה תלמד:

• חיפוש בינארי
• סימון ביג או
• קוד ציווי
• רקורסיה
• רקורסיבי זנב
• פיצול מערך
• מבט מערך
• חֲלוּקָה

כל אלגוריתם נלמד בשלושה שלבים:

• הדרכה: ג'ונתן מציג את האלגוריתם מבחינה רעיונית.
• יישום: אנו מלכלכים את ידינו על ידי יצירת גרסאות משלנו לאלגוריתם.
• פתרון: ג'ונתן מראה לנו את היישום שלו לצורך השוואה.

תנאים מוקדמים

תוכלו להפיק את המרב מהקורס אם יש לכם הבנה טובה ב- Javascript ואתם אידיאליים כבר עובדים כמפתחים או שהם בוגרי Bootcamp.

אם אתה עדיין לא שם, עיין במדריכים החינמיים הנהדרים של Scrimba מבוא ל- JavaScript ומבוא ל- ES6 +.

מבוא למדריך

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

עם לקוחות הכוללים חברות כמו נאס"א ו- HP, הוא רק האדם שיעביר אותך במסע הלמידה. אז בואו נתחיל!

חיפוש בינארי

לחץ על התמונה כדי לגשת לקורס.

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

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

חיפוש בינארי הוא אחת מכמה אסטרטגיות למענה על השאלה "היכן האלמנט הזה מופיע ברשימה?"

כשעונים על השאלה ישנן שתי גישות עיקריות:

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

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

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

בעוד שלגישת המטאטא יש זמן ריצה לינארי (ראה גרף לעיל) ו- Big O של O (n), לגישת המפצל יש זמן ריצה תת ליניארי ו- Big O של O (log n).

הֶכְרֵחִי

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

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

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

רקורסיה

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

ג'וננתן מניע אותנו עם גרסת שלד לפיתרון ואז מעודד אותנו לנסות את האתגר לבד:

let binarySearchWithRecursion = (array, element, compare = defaultCompare) => { return -1; }; export default binarySearchWithRecursion; 

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

רקורסיבי זנב

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

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

פיצול מערך

If you completed the previous challenge, you may have felt that we're still passing a lot of extra information into our binary search via recursion. This cast looks at a way of cleaning that up called array splitting.

We can think of array splitting in terms of our phone book example from earlier - whenever we decide that half the phone book is irrelevant, we just tear it off and throw it away. Similarly, our next solution should disregard any parts of the array which don't include our desired entry.

To help us achieve this, Jonathan starts us off with some skeleton code:

let binarySearchWithArraySplitting = ( array, element, compare = defaultCompare ) => { return -1; }; 

Then, as usual, he gives us free rein to try to the solution for ourselves before walking us through his own implementation.

Although this is an elegant method of binary search, because it involves making a copy of part of the array, it no longer has a Big O of O(n) and has a higher memory usage and slower run time. Continue with the course to find out whether there is a way to regain a higher performance with a similar code solution...

Array View

In this cast, we look for ways of merging the higher performance of our previous solutions with the elegance of array splitting. To do this, we create an array-like object that responds to the same methods as an array. We'll then inject this object in place of the original array.

Jonathan gets us started by initializing a function ArrayView which returns an object that expects three arguments: array, start and end. When invoked, ArrayView should return an object with four methods, length, toArray, slice and get.

export let ArrayView = ( array, start = 0, end = array.length, ) => ({ length: end - start, toArray: () => array.slice(start, end), slice: () => , get: () => , }); let binarySearchWithArrayView = (array, ...args) => binarySearchWithArraySplitting(ArrayView(array), ...args) 

Our challenge is to implement the slice and get methods of ArrayView without making a copy of the original array. Click through to try it out and then view Jonathan's walkthrough.

Although this solution produces better, more readable code, it is longer than some of our previous solutions. Continue with the course to find out if we can retain the benefits of ArrayView while lifting even more of the logic out of binary search code...

Array Partition

In the final challenge cast of the course, Jonathan gives us a goal of extracting some of the cryptic bounce logic in our previous version into a data structure.

For this, we need a simple data structure which returns the middle, left or right part of an array. To start us off, Jonathan sets up a function ArrayPartition:

export let ArrayPartition = (array, pivot) => ({ left: () => array.slice(0, pivot), middle: () => array.get(pivot), right: () => array.slice(pivot + 1, array.length), }); 

Next, Jonathan sets up a new version of binary search called binarySearchWithPartition, which has a starting signature the same as binarySearchWithArraySplitting:

let binarySearchWithPartition = (array, element, compare = defaultCompare) => { if (array.length === 0) { return -1; } const middle = Math.floor(array.length / 2); const comparison = compare(element, array.get(middle)); if (comparison === 0) { return middle; } //bounce logic const [left, right] = comparison === -1 ? [0, middle - 1] : [middle + 1, array.length]; //end of bounce logic const subIndex = binarySearchWithArraySplitting( array.slice(left, right), element, compare ); return subIndex === -1 ? -1 : left + subIndex; }; let binarySearchWithPartitionAndView = (array, ...args) => binarySearchWithPartition(ArrayView(array), ...args); 

Our challenge now is to rewrite binarySearchWithPartition with none of the bounce logic highlighted above, instead of creating an array partition and making calls to its left, middle and right methods.

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

לעטוף

הגעתם לסוף הקורס - עבודה נהדרת! סקרנו כמה גישות לחיפוש בינארי, כולם עם יתרונות וחסרונות משלהם, ובנינו זיכרון שרירים נהדר לעבודה יעילה עם אלגוריתמים.

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

הקורס המלא של ג'ונתן הכולל 10 אלגוריתמים יעלה בסוף השנה, אך בינתיים, אני מקווה שתוכלו להשתמש בכישורי החיפוש הבינאריים החדשים שלכם.

קידוד שמח :)