پیاده سازی جستجوی دودویی

[fandogh]

سلام. من میخوام با روش جستجوی دودویی تعدادی عدد رو در یک لیست جستجو کنم، درصورتی که توی اون لیست وجود نداشته باشن، در مکان مناسب درج بشن، طوری که ترتیب اون اعداد حفظ بشه. اگر برای پیاده سازی از لیست پیوندی استفاده کنم، آیا برای جستجو لازمه که کل لیست پیمایش بشه؟ در اینصورت نمیتونم به پیچیدگی زمانی log n برسم. به خاطر درج داده جدید از آرایه هم نمیشه استفاده کرد. لطفا راهنمایی کنید چطور می تونم پیاده سازی رو انجام بدم

[aqm176]

سلام و خسته نباشید.

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

برای جستجوی دودویی، زمانی شما به log n میرسی که مرتب سازی شده باشن.

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

ضمنا اینم توجه داشته باش که دو طرفه باشه لیستت.