الگوریتم binary search

الگوریتم جستجوی دودویی یا (binary search algorithm) جزو الگوریتم های جستجوی مرتب به شمار میره که برای یافتن یک مقدار خاص توی یک آرایه ی مرتب استفده میشه.

به طور کلی این الگوریتم با دریافت یک آرایه ی و یک مقدار هدف، اون مقدار رو توی آرایه پیدا میکنه. نحوه ی کار این الگوریتم به این صورته که وسط آرایه رو پیدا میکنه و بررسی میکنه که آیا از مقدار هدف بزرگتره یا کوچکتر (یا مساوی) که اگر بزرگتر بود، اینبار همین کار رو روی نصفه ی اول و اگر کوچکتر بود روی نصفه ی دوم آرایه انجام میده.

تصویر سازی

ما اینجا میخوایم با یک آرایه متشکل از 7 عدد [1,3,4,5,6,8,12] که به ترتیب توی آرایه قرار گرفتن بهتون نشون بدیم الگوریتم binary search چیه.

خب هدف ما یا همون target عدد 8 هست. یعنی میخوایم ببینیم 8 کجای این آرایه قرار داره؟ (یا اصلا وجود داره یا نه؟)

یکم شاید اولش پیچیده به نظر بیاد اما بذارید روی تصویر بهتون نشون بدم.

کد بازی

خب حالا دقیقا مثل بخش قبل ما یک آرایه داریم متشکل از 7 عدد [1,3,4,5,6,8,12] که به ترتیب توی آرایه قرار گرفتن.

و همچنین میخوایم ببینیم عدد 8 کجای آرایه قرار داره.

const arr = [1, 3, 4, 5, 6, 8, 12];
const target = 8;

کاری که ابتدا انجام میدیم، میایم وسط آرایه رو پیدا میکنیم، خب چون میدونیم آرایه ی ما 7 عضو داره، پس عضو سوم میشه وسط آرایه. اما تو برنامه نویسی ما باید به برنامه بگیم که برامون وسط آرایه رو بدست بیاره، چون همیشه که آرایه ی 7 عضوی نداریم…

برای این کار ایندکس اول آرایه و ایندکس آخر آرایه رو جمع میکنیم و تقسیم بر 2 میکنیم. از اونجا که ممکنه عددمون صحیح نباشه، رو به پایین رندش می کنیم.

ایندکس اول که مشخصه، صفره، ولی ایندکس آخر چی؟ خب برای بدست آوردنش راه های زیادی هست، ما اینجا میایم طول آرایه رو میگیریم و منهای 1 می کنیم تا ایندکس آخرمون بدست بیاد.

پس توی زبان جاوا اسکریپت اینطوری می نویسیم.

// میانه ی آرایه به این صورت به دست می آید
let firstIndex = 0;
let lastIndex = arr.length - 1 // 6

let middle = (firstIndex + lastIndex) / 2; // 3

// حالا رو به پایین گردش میکنیم
// که مطمئن بشیم بهمون عدد صحیح میده
middle = Math.floor(middle) // 3

خب حالا که میانه ی آرایه رو پیدا کردیم میایم مقدارش رو میگیریم و بررسی میکنیم که بدونیم تو چه وضعیتی هستیم.

سه حالت ممکنه پیش بیاد:

1. عدد یافت شده برابر با عدد target میشه
2. عدد یافت شده بزرگتر از عدد target میشه
3. عدد یافت شده کوچکتر از عدد target میشه

if(target === arr[middle]){
	console.log("مقدار در ایندکس " + middle + " یافت شد");
} else if (target > arr[middle]){
	console.log("جستجو رو در نیمه ی چپ آرایه ادامه بده");
  	firstIndex = middle + 1
} else {
 	console.log("جستجو رو در نیمه ی راست آرایه ادامه بده");
  	lastIndex = middle - 1
}

خب کاری که ما تو این مرحله انجام دادیم این بود که اومدیم گفتیم اون مقدار وسط که ایندکسش رو پیدا کردیم بررسی کن.

اگر مقدار target برابر با اون مقدار وسط باشه، پس مکان targetرو توی آرایه پیدا کردیم

اگر مقدار target بزرگتر از اون مقدار وسط باشه، از اونجایی که آرایه ی ما به ترتیب چیده شده، پس خیالمون راحته که تو نصفه ی اول وجود نداره، در نتیجه توی نصفه ی دوم باید دنبالش بگردیم. برای این کار، خب انتهای آرایه رو که داریم، منتها ابتداش میشه از بعد از این ایندکسی که داریم بررسیش میکنیم. پس میایم میگیم ابتدای ایندکسی که میخوای بگردی رو بذار روی middle + 1

اگر مقدار target کوچکتر از اون مقدار وسط بود هم دقیقا برعکس بالا عمل میکنیم و توی نصفه ی اول دنبال مقدارمون میگردیم، ولی اینبار با ایندکس ابتدایی کار نداریم و میگیم ایندکس پایانی رو برامون بذار روی middle - 1

جز حالت اول که ما باید برنامه رو متوقف کنیم، در باقی حالات ما یک firstIndex و یا lastIndex جدید داریم. پس دوباره میایم و مراحل بالا رو با ایندکس های جدید انجام میدیم.

درسته! یکم احمقانه س که بخوایم دوباره انجامش بدیم، چون تو برنامه نویسی معجزه ی حلقه ها رو داریم.

پس به شکل زیر بازنویسیش می کنیم.

const arr = [1, 3, 4, 5, 6, 8, 12];
const target = 8;

let firstIndex = 0;
let lastIndex = arr.length - 1;


while (firstIndex <= lastIndex){
  // ،چون هر بار باید ایندکس وسط رو حساب کنیم
  // از این قسمت داخل حلقه قرار میدیم
  let middle = Math.floor((firstIndex + lastIndex) / 2);
  
  //شرطمون رو هم که درست مثل بالا مینویسیم
  if(target === arr[middle]){
	console.log("مقدار در ایندکس " + middle + " یافت شد");
    break; // واسه این که حلقه متوقف بشه
  } else if (target > arr[middle]){
	console.log("جستجو رو در نیمه ی چپ آرایه ادامه بده");
  	firstIndex = middle + 1
  } else {
 	console.log("جستجو رو در نیمه ی راست آرایه ادامه بده");
  	lastIndex = middle - 1
  }
  
}

خب تقریبا کارمون تموم شد. فقط برای این که بشه از این الگوریتم دوباره استفاده کرد بهتره که بیایم و توی یک تابع قرارش بدیم.

پس به شکل زیر باز نویسی می کنیم.

const binarySearch = (array, target) => {
  let firstIndex = 0;
  let lastIndex = array.length - 1;

  while (firstIndex <= lastIndex){
    let middle = Math.floor((firstIndex + lastIndex) / 2); // 3

    if(target === array[middle]){
	  return middle; // ایندکس مقدار هدف
    } else if (target > array[middle]){
      firstIndex = middle + 1
    } else {
      lastIndex = middle - 1
    }
  }
  
  return -1; // مقدار هدف در آرایه وجود ندارد
}

const arr = [1, 3, 4, 5, 6, 8, 12];

const target = 8;
binarySearch(arr, target); // 5

const target2 = 2;
binarySearch(arr, target2); // -1 

البته این نکته رو بگم که توی اکثر زبان های برنامه نویسی سطح بالا شما نیاز به الگوریتم پیدا نمی کنید و فانکشن ها براتون کار رو انجام میدن، اما دونستن الگوریتم به شما برای درک بهتر مفاهیم برنامه نویسی کمک میکنن و شما رو از یک کد نویس به یک برنامه نویس تبدیل میکنن.