نحوه کدنویسی الگوریتم جستجوی باینری

ek3nk4r 2023-04-28

0 37 خواندن این مطلب 7 دقیقه زمان میبرد

پیشنهاد ویژه

خرید فالوور واقعی خرید لایک اینستاگرام خرید ویو اینستاگرام خرید فالوور اینستاگرام

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

این مقاله در ابتدا در jarednielsen.com منتشر شده است

فهرست مطالب

نحوه کدنویسی الگوریتم جستجوی باینری در جاوا اسکریپت و پایتون

برنامه نویسی حل مسئله است. برای حل هر مشکل برنامه نویسی باید چهار مرحله را طی کنیم:

مشکل را درک کنید
ایجاد یک طرح
طرح را اجرا کنید
طرح را ارزیابی کنید

مشکل را درک کنید

برای درک مشکل خود ابتدا باید آن را تعریف کنیم. بیایید دوباره مشکل را به عنوان معیار پذیرش در نظر بگیریم:

GIVEN a sorted array
WHEN I request a specific value
THEN I am returned the location of that value in the array

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

بیایید برنامه ریزی کنیم!

ایجاد یک طرح

بیایید اکتشافات تفکر محاسباتی خود را مجدداً مرور کنیم زیرا آنها در ساختن یک برنامه کمک می کنند و راهنمایی می کنند. آن ها هستند:

تجزیه
الگو شناسی
انتزاع – مفهوم – برداشت
طراحی الگوریتم

اولین گام تجزیه، یا تجزیه مشکل ما به مشکلات کوچکتر است. کوچکترین مشکلی که می توانیم حل کنیم چیست؟

آرایه ای حاوی یکی شماره، به عنوان مثال: [1].

بیایید این را رمزگذاری کنیم:

INPUT arr, num

IF arr[0] == num
    RETURN 'Bingo!'
ELSE 
    RETURN FALSE

این کمتر از الف است جستجو کردن و بیشتر از یک بازی حدس زدن. کوچکترین مشکل بعدی چیست؟ آرایه ای حاوی دو شماره: [1, 2].

INPUT arr, num

IF arr[0] == num
    RETURN 'Found num in the 0 index`
ELSE IF arr[1] == num
    RETURN 'Found num in the 1 index`
ELSE 
    RETURN FALSE

این هنوز یک بازی حدس زدن است، اما اکنون باینری است! وقتی آن دو شرط را نوشتیم چه کردیم؟ مشکل را نصف کردیم: [1] و [2].

بیایید یکی دیگر را اضافه کنیم: [1, 2, 4]. حالا چی؟ ما میتوانست برای هر شاخص شرط بنویسید، اما آیا مقیاس می شود؟

آیا می توانیم این آرایه را از وسط نصف کنیم؟ تمیز نیست.

اما ما می توان شاخص را در وسط انتخاب کنید و بررسی کنید که آیا بزرگتر یا کوچکتر از آن است num. اگر num کمتر از شاخص متوسط است، خواهیم کرد محوری و مقدار قبلی را مقایسه کنید و اگر num بزرگتر از شاخص میانی است، خواهیم کرد محوری و مقدار بعدی را بررسی کنید. سلام! بیایید این شاخص را بنامیم محوری.

اگر آرایه ما باشد [1, 2, 4]، ما pivot است 2. بیایید این را رمزگذاری کنیم:

INPUT arr, num

SET pivot TO arr[1]

IF arr[pivot] == num
    RETURN 'Found num at pivot'
ELSE IF arr[pivot] < num
    RETURN 'Found num in the 0 index'
ELSE 
    RETURN 'It's gotta be in the 2 index...'

بیایید با یک آرایه کمی بزرگتر کار کنیم: [1, 2, 4, 8].

چند مشکل کوچک وجود دارد که باید در اینجا حل کنیم:

به منظور مقیاس، ما دیگر نمی توانیم مقدار ذخیره شده در آن را “کد سخت” کنیم pivot.
هیچ “شاخص میانی” وجود ندارد. پس برای چه ارزشی انتخاب می کنیم pivot?

بیایید ابتدا به مشکل اول بپردازیم: به سادگی می توانیم آرایه را به دو قسمت تقسیم کنیم.

INPUT arr, num

SET pivot TO LENGTH OF arr DIVIDED BY 2

IF arr[pivot] == num
    RETURN 'Found num at pivot'
ELSE IF arr[pivot] < num
    RETURN 'Found num in the 0 index'
ELSE 
    RETURN 'It's gotta be in the 2 index...'

با استفاده از مثال بالا، آرایه ما شامل چهار عنصر است. اگر طول آرایه خود را بر دو تقسیم کنیم، pivot برابر 2 خواهد بود.

اگر pivot برابر 2 است، مقدار آن شاخص در آرایه ما برابر است 4.

اما اگر تعداد فرد عنصر در آرایه وجود داشته باشد چه؟

[1, 2, 3, 4, 5]

اگر طول آرایه را بر 2 تقسیم کنیم، 2.5 به دست می آید.

ما فقط باید به بالا یا پایین جمع کنیم. بیایید گرد کنیم. کد شبه ما اکنون می‌خواند:

INPUT arr, num

SET pivot TO THE FLOOR OF THE LENGTH OF arr DIVIDED BY 2

IF arr[pivot] == num
    RETURN 'Found num at pivot'
ELSE IF arr[pivot] < num
    RETURN 'Found num in the 0 index'
ELSE 
    RETURN 'It's gotta be in the 2 index...'

وقتی طول این آرایه را بر 2 تقسیم می کنیم و مقدار برگشتی را طبقه بندی می کنیم، ما pivot برابر با 2 است.

مقدار ذخیره شده در شاخص 2 است 3.

قبلاً، چک‌های مشروط را در دو طرف پیوت کدگذاری می‌کردیم. آیا اینجا کار می کند؟

نه، چون الان وجود دارد دو مقادیری که باید در دو طرف محور خود بررسی کنیم.

زمان تکرار فرا رسیده است!

چون نمی دانیم حلقه ما چقدر باید اجرا شود، از a استفاده می کنیم while. ما while حلقه ها به یک شرطی نیاز دارند. در اینجا از چه چیزی می خواهیم استفاده کنیم؟

اگر pivot کمتر است از num، سپس در تکرار بعدی باید با مقداری بزرگتر از شروع کنیم pivot. اما ما باید مطمئن شویم که هنوز در حال بررسی هستیم همه از مقادیر بیشتر از pivot.

و اگر pivot بزرگتر است از num، سپس در تکرار بعدی باید با مقدار کمتر از شروع کنیم pivot. و همانطور که در بالا ذکر شد، باید مطمئن شویم که هنوز در حال بررسی هستیم همه از مقادیر کمتر از pivot.

آیا الگو را می بینید؟

قبل از اینکه ما را اجرا کنیم while تکرار، بیایید این شرط ها را به شبه کد ترجمه کنیم:

INPUT arr, num

SET pivot TO THE FLOOR OF THE LENGTH OF arr DIVIDED BY 2

IF arr[pivot] == num
    RETURN 'Found num at pivot'
ELSE IF arr[pivot] < num
    START SEARCHING IN THE NEXT ITERATION AT pivot + 1
ELSE 
    SEARCH UP TO pivot - 1 IN THE NEXT ITERATION

بیایید با استفاده از آرایه پنج عنصری خود و جستجوی یک سناریوی فرضی قدم بگذاریم 5.

در اولین تکرار، تنظیم کردیم pivot به 3.

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

در تکرار بعدی، ما شروع به جستجو در pivot + 1، که است 4.

در تکرار بعدی چه اتفاقی می افتد؟

تنظیم کردیم pivot به کف طول آرایه ما تقسیم بر 2 که برابر 2 است.

سلام! صبر کن! ما قبلاً این مقدار را بررسی کردیم.

ما به یک جدید نیاز داریم pivot.

باید a را تنظیم کنیم pivot از مقادیر باقیمانده که باید بررسی شوند. در مورد ما، این است:

[4, 5]

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

اینجا چیکار کنیم؟

ما انتزاعی می شویم!

بیایید متغیرهایی را برای ذخیره این مقادیر در هر تکرار اعلام کنیم:

SET start index TO 0
SET end index TO THE LENGTH OF THE ARRAY - 1

در نهایت، باید عبارات شرطی خود را تغییر دهیم تا این مقادیر را در هر تکرار مجدداً اختصاص دهیم:

INPUT arr, num

SET start index TO 0
SET end index TO THE LENGTH OF THE ARRAY - 1

WHILE
    SET pivot TO THE FLOOR OF THE LENGTH OF arr DIVIDED BY 2

    IF arr[pivot] == num
        RETURN 'Found num at pivot'
    ELSE IF arr[pivot] < num
        SET start index TO pivot + 1
    ELSE 
        SET end index TO pivot - 1 
RETURN FALSE

طرح را اجرا کنید

اکنون فقط موضوع ترجمه شبه کد ما به نحو زبان برنامه نویسی ما است.

نحوه کدنویسی الگوریتم جستجوی باینری در جاوا اسکریپت

بیایید با جاوا اسکریپت شروع کنیم…

const powers = [1, 2, 4, 8 ,16, 32, 64, 128, 256, 512];

const binarySearch = (arr, num) => {

   let startIndex = 0;
   let endIndex = (arr.length)-1;

   while (startIndex <= endIndex){

       let pivot = Math.floor((startIndex + endIndex)/2);

       if (arr[pivot] === num){
            return `Found ${num} at ${pivot}`;
       } else if (arr[pivot] < num){
           startIndex = pivot + 1;
       } else {
           endIndex = pivot - 1;
       }
   }
   return false;
}

نحوه کدنویسی الگوریتم جستجوی باینری در پایتون

حالا بیایید آن را در پایتون ببینیم …

import math

powers = [1, 2, 4, 8 ,16, 32, 64, 128, 256, 512]

def binarySearch(arr, num):

   startIndex = 0
   endIndex = len(arr)-1

   while (startIndex <= endIndex):

       pivot = math.floor((startIndex + endIndex)/2)

       if (arr[pivot] == num):
            return f"Found {num} at index {pivot}"
       elif (arr[pivot] < num):
           startIndex = pivot + 1
       else:
           endIndex = pivot - 1

   return false

طرح را ارزیابی کنید

آیا می توانیم بهتر عمل کنیم؟

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