آموزش برنامه نویسی به زبان ++C

این وبلاگ جهت آموزش برنامه نویسی به زبان ++C برای دانش آموزان دبیرستان فرزانگان ایجاد شده است.

۱ مطلب با موضوع «binary search» ثبت شده است

برای جستجوی یک عدد در یک آرایه، راحت ترین راه این است که عدد مورد نظر را با تمام خانه های موجود در آرایه مقایسه کنیم. 

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

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

ابتدا عدد مورد نظر یا f را با خانه ی وسطی آرایه مقایسه میکنیم. خانه ی وسطی آرایه از مجموع دو مقدار start و end بدست می آید. start یعنی آغاز بخشی از آرایه که میخواهیم در آن جستجو کنیم که در اول کار 0 است. end یعنی پایان بخشی از آرایه که میخواهیم در آن جستجو کنیم که در ابتدا n-1 است. ( یعنی در فاز اول جستجو میخواهیم همه ی آرایه را در نظر داشته باشیم) 

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

اما اگر F از مقدار وسطی بزرگتر بود باید تکه ی اول آرایه را بگردیم( چون ارایه ما از بزرگ به کوچک مرتب شده است) پس نقطه ی آغاز تغییری نمیکند. ( همان 0 است) اما نقطه ی پایان به قبل از mid کاهش پیدا میکند و برابر mid-1 می شود. 

اگر f از مقدار وسطی یا mid کوچکتر بود باید نیمه ی دوم آرایه را بگردیم که در آن صورت مقدار end یا پایان تغییری نمیکند و n-1 است. اما نقطه ی آغاز تغییر میکند و به خانه ی بعد از خانه ی وسطی  یا mid+1 افزایش پیدا میکند. 

۲۸ سوال موافقین ۱ مخالفین ۰ ۱۶ آذر ۹۱ ، ۱۸:۲۱
سارا نازاری