جستجوی باینری یا دودویی
برای جستجوی یک عدد در یک آرایه، راحت ترین راه این است که عدد مورد نظر را با تمام خانه های موجود در آرایه مقایسه کنیم.
اما اگر بخواهیم برنامه ای بهینه تر بنویسیم که سرعت بالاتری داشته باشد باید آرایه را ابتدا با یکی از روشهای مرتب سازی، مرتب کنیم.
در برنامه ی زیر آرایه از بزرگ به کوچک با روش مرتب سازی حبابی، مرتب شده است. پس از آن می توانیم به شیوه ی زیر که به جستجوی دودویی شناخته شده است عمل کنیم:
ابتدا عدد مورد نظر یا f را با خانه ی وسطی آرایه مقایسه میکنیم. خانه ی وسطی آرایه از مجموع دو مقدار start و end بدست می آید. start یعنی آغاز بخشی از آرایه که میخواهیم در آن جستجو کنیم که در اول کار 0 است. end یعنی پایان بخشی از آرایه که میخواهیم در آن جستجو کنیم که در ابتدا n-1 است. ( یعنی در فاز اول جستجو میخواهیم همه ی آرایه را در نظر داشته باشیم)
بعد از مقایسه با خانه ی وسطی اگر f دقیقا همان خانه بود که کار تمام است و فقط باید شماره ی خانه ی وسطی(mid) را نمایش دهیم.
اما اگر F از مقدار وسطی بزرگتر بود باید تکه ی اول آرایه را بگردیم( چون ارایه ما از بزرگ به کوچک مرتب شده است) پس نقطه ی آغاز تغییری نمیکند. ( همان 0 است) اما نقطه ی پایان به قبل از mid کاهش پیدا میکند و برابر mid-1 می شود.
اگر f از مقدار وسطی یا mid کوچکتر بود باید نیمه ی دوم آرایه را بگردیم که در آن صورت مقدار end یا پایان تغییری نمیکند و n-1 است. اما نقطه ی آغاز تغییر میکند و به خانه ی بعد از خانه ی وسطی یا mid+1 افزایش پیدا میکند.
خب تا اینجای کار فهمیدیم که f در کدام سمت آرایه قرار دارد. قسمت انتهایی یا ابتدایی.
اعین این فرآیند باید برای آن قسمتی که f در آن قرار دارد، یعنی مثلا قسمت ایتدایی، نیز دوباره اجرا شود. پس می توانیم که نتیجه بگیریم که این فرآیند را باید در حلقه ای قرار دهیم که شرط حلقه این است : start<=end
یعنی تا زمانی ادامه میدهیم که start از end بزرگتر نشود و از آن رد نشود تا در حلقه بینهایت گیر نکنیم!
پس از اتمام حلقه اگر start ازend بزرگتر شده بود یعنی همه ی آرایه را گشته و f را پیدا نکرده و start از روی end رد شده است. پس f در آرایه نبوده و باید پیغام مناسبی مبنی بر وجود نداشتن F در آرایه چاپ شود.
برنامه رو میتونید در ادامه مطلب ببینید ......
ضمنا این عکس به فرمت GIF کمک زیادی می کنه دانلود و با اینترنت اکسپلورر باز کنید
:: موضوعات مرتبط:
الگوریتم ,
,
:: برچسب‌ها:
اگوریتم جستجوی دو دویی ,
:: بازدید از این مطلب : 579
|
امتیاز مطلب : 4
|
تعداد امتیازدهندگان : 1
|
مجموع امتیاز : 1
عضو شوید
عضویت سریع
آمار
وب سایت:
آمار مطالب
آمار بازدید
