هنرجو | آموزش تخصصی رشته های هنرستان
جستجو يکی از مهمترين وظايف برنامه های کامپيوتری می باشد. به عنوان مثال دفتر تلفنی که به دنبال نام فردی در آن می گرديم و يا جستجوی نام يک دانشجو در ليست دانشجويان یک کلاس درس را در نظر بگیرید، در مثال های ذکر شده نیاز به انجام جستجو در بین داده ها می باشد. در اين مبحث دو روش جستجو را مورد بررسی قرار می دهيم:
- جستجوی خطی
- جستجوی دودویی
جستجوی خطی در آرايه های نا مرتب مورد استفاده قرار می گيرد اما جستجوی دودویی در آرايه های مرتب استفاده می شود. در روش جستجوی خطی، عنصر مورد جستجو با هر يک از عناصر آرايه مقايسه می شود، در صورتی که دو عنصر برابر بودند، عمل جستجو به پايان می رسد و انديس عنصر برگردانده می شود در غیر اینصورت مقايسه با عنصر بعدی آرايه انجام می شود.
در روش جستجوی دودویی آرایه باید از قبل مرتب باشد. در اين روش، در هر بار مقايسه، نيمی از عناصر آرايه حذف می شوند . الگوريتم عنصر ميانی آرايه را می يابد و آن را با عنصر مورد جستجو، مقايسه می کند. اگر برابر بودند، جستجو به پايان رسيده و انديس عنصر برگردانده می شود، در غير اين صورت عمل جستجو روی نيمی از عناصر آرایه انجام می گيرد. اگر عنصر مورد جستجو کوچکتر از عنصر ميانی باشد، جستجو روی نيمه اول آرايه، در غير اين صورت روی نيمه دوم آرايه انجام می شود. اين جستجوی جديد روی زير آرايه طبق الگوريتم جستجو روی آرايه اصلی انجام می شود يعنی عنصر ميانی زير آرايه يافته می شود و با عنصر مورد جستجو مقايسه می گردد، اگر برابر نباشند زير آرايه مجدداً نصف می شود و در هر بار جستجو زير آرايه ها کوچکتر می شوند. عمل جستجو تا يافتن عنصر مورد نظر و يا نيافتن عنصر مورد نظر ادامه می يابد. در ویدیوی زیر این دو روش جستجو به زبان ساده توضیح داده شده است.
