>> ZAMYLA CHAN: اولین چیزی که شما ممکن است اطلاع در مورد پیدا کردن این است که ما در حال حاضر
کد نوشته شده برای ما.
این کد توزیع نامیده می شود.
بنابراین ما نه فقط نوشتن خود ما کد از ابتدا دیگر.
در عوض، ما در حال پر کردن فضاهای خالی در برخی از کد موجود از قبل.
>> برنامه find.c دهید برای اعداد برای پر کردن کومه علف خشک، جستجو
انبار کاه برای یک سوزن کاربر را مشاهده کنید، و این کار با تماس با مرتب کردن و
جستجو، توابع تعریف شده در helpers.c.
بنابراین find.c نوشته شده است در حال حاضر.
کار شما این است که ارسال یاران.
>> پس چه کار می کنیم؟
ما در حال اجرای دو تابع.
جستجو، جایی که بازگرداندن true اگر مقدار در انبار کاه یافت، بازگشت
نادرست است اگر ارزش است در انبار کاه نیست.
و سپس ما نیز پیاده سازی مرتب سازی بر، که انواع آرایه به نام ارزش ها.
بنابراین اجازه دهید مقابله با جستجو.
>> جست و جو در حال حاضر اجرا به عنوان یک جستجوی خطی.
اما شما می توانید بسیار بهتر از آن انجام دهد.
جستجو خطی در O از N اجرا زمان است که کاملا آرام، با وجود آن که
می توانید هر لیست داده شده به آن را جستجو کنید.
کار شما این است برای اجرای جستجوی دودویی، تا آن زمان O از ورود به سیستم نفر اجرا شود.
که بسیار سریع می باشد.
>> اما یک شرط وجود دارد.
جستجوی دودویی تنها می توانید جستجو از طریق لیست های از پیش طبقه بندی شده اند.
چرا؟
خوب، اجازه دهید نگاهی به عنوان مثال.
با توجه به مجموعه ای از ارزش ها، کومه علف خشک، ما قصد داریم به دنبال
برای یک سوزن، و در این به عنوان مثال، عدد صحیح 3.
>> راه که جستجوی دودویی کار می کند این است که ما مقدار متوسط ​​از مقایسه
آرایه به سوزن، بسیار شبیه به نحوه ما یک دفترچه تلفن به وسط باز
صفحه در هفته 0.
بنابراین پس از مقایسه مقدار عمق به سوزن، شما هم می توانید دور انداختن
سمت چپ و یا نیمه سمت راست از آرایه با سفت مرزهای خود را.
در این مورد، از 3، سوزن ما، کمتر از 10، مقدار متوسط،
سمت راست حد می تواند کاهش دهد.
>> اما سعی کنید به مرزهای شما به عنوان تنگ که ممکن است.
اگر مقدار متوسط ​​است سوزن نیست، سپس شما می دانید که شما لازم نیست
آن را در جستجوی خود را.
پس حق خود را موظف می سفت محدوده جستجو فقط کمی بیشتر،
و غیره و غیره، تا زمانی که شما سوزن خود را پیدا کنید.
>> پس چه شبه کد شکلی بود؟
خب، در حالی که ما هنوز به دنبال از طریق لیست و هنوز هم
عناصر به نگاه در، ما را به وسط لیست و مقایسه آن
مقدار عمق به سوزن است.
اگر آنها برابر است، پس این بدان معناست که ما کرده ایم پیدا سوزن، و ما می توانیم
بازگشت درست است.
>> در غیر این صورت، اگر سوزن کمتر از است مقدار متوسط، پس از آن که به معنی ما
می تواند در نیمه سمت راست فقط دور و جستجو در سمت چپ آرایه.
در غیر این صورت، ما به جستجو سمت راست از آرایه.
و در پایان، اگر شما هیچ کدام ندارد عناصر چپ به جستجو، اما شما
اند سوزن خود را پیدا نکرده است، سپس شما بازگشت کاذب.
از آنجا که سوزن قطعا در انبار کاه نیست.
>> در حال حاضر، یک چیز شسته و رفته در مورد این شبه کد را که در جستجوی دودویی است که می تواند
توان هم به صورت تکرار شونده تفسیر و یا پیاده سازی بازگشتی.
بنابراین این امر می تواند بازگشتی اگر شما به نام تابع جستجو در جستجو
عمل در هر نیمه از آرایه.
ما به بازگشت کمی را پوشش می دهند بعد از آن در دوره.
اما نمی دانم که این یک گزینه است اگر شما می خواهم را امتحان کنید.