מערך - מציאת איבר

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

עבור מערך ממוין נבצע חיפוש בינארי. חיפוש בינארי הוא חיפוש כזה: תחילה נבדוק את האיבר האמצעי, אם ערכו גדול מערך האיבר שאנו מחפשים נדע שהאיבר נמצא בחצי התחתון, אם ערכו קטן מהערך המבוקש נחפש בחצי העליון. אם הערכים זהים, אזי מצאנו את האיבר. כך נמשיך כל פעם על חצי המערך הרלוונטי, עד למציאת האיבר. מכיוון שבכל פעם טווח החיפוש קטן בחצי, לאחר (LOG(N פעולות נגיע לטווח חיפוש של 1. היעילות אם כן היא (LOG(N.

הדגמה ויזואלית - חיפוש בינארי

פסאודו קוד עבור חיפוש רגיל

function find(Ar, x)
  for i=1 to length(Ar)
    if Ar[i]==x return i
  return "not found"

פסאודו קוד עבור חיפוש בינארי

function binary_search(Ar, x)
  low <-- 1
  high <-- length(Ar)
  while low <= high
     mid <-- (low+high)/2
     if Ar[mid]==x
       return mid
     else if Ar[mid]<x
       high <-- mid-1
     else if Ar[mid]>x
       low <-- mid+1
  return "not found"