חיפוש

שיעור 20 מתוך 23 בקורס C++ - ספריית התבניות הסטנדרטית של Coddy.

חיפוש הוא תהליך של איתור מיקום של איבר מסוים ברצף של איברים.

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

יש מספר טכניקות ושיטות חיפוש, אבל ב-C++ תלמדו על:

חיפוש ליניארי
חיפוש בינארי

חיפוש ליניארי

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

Linear Search(sequence, key)
	for each item in sequence:
		if item == key
			return item's index

בקוד אמיתי, החיפוש הליניארי ייראה בערך כך:

int linear_search(int array[], int n, int x)
{
	for(int i = 0; i < n; i++)
		if(array[i] == x)
			return i;
	return 0;
}

int main()
{
	int array[] = {1, 2, 3, 4, 5};
	int n = 5;
	int x = 3;
	
	cout << "The index of the element " << x << " is " << linear_search(array, n, x);

Output:
The index of the element 3 is 2

כפי שאפשר לראות בקוד שלמעלה, פונקציית החיפוש הליניארי עוברת בלולאה על רצף האיברים עד שהיא מוצאת התאמה. אם היא לא מוצאת התאמה, היא מחזירה ‎-1.

חיפוש בינארי

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

נניח שאנחנו מחפשים את האיבר x = 4

כך ייראה הקוד לחיפוש בינארי.

int binarySearch(int array[], int x, int left, int right) {
  
  while (left <= right) {
    int mid = left + (right - left) / 2;

    if (array[mid] == x)
      return mid;

    if (array[mid] < x)
      left = mid + 1;

    else
      right  = mid - 1;
  }

  return -1;
}

int main()
{
    int array[] = {1, 5, 8, 10, 20};
    int x = 10;
    int n = 5;
    int result = binarySearch(array, x, 0, n - 1);
    
    if(result == -1)
    	cout << "Not found.";
    else
    	cout << "The element is found at " << result;

Output:
The element is found at 3

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

אתגר

בינוני

נתונים לך 10 מספרים מהקלט. בשורה הבאה מופיע מספר N. בשורה השלישית מופיעים N מספרים שמייצגים את המיקומים של האיברים שעליך להציג על המסך.

קלט
10 20 30 40 50 60 70 80 90 100
3
20
50
80

פלט
1 4 7

נסו בעצמכם

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

// Enter your code here

int main()
{
    // Enter your code here

    return 0;
}