05-24-2012، 10:17 PM
در این روش جستجو حتما باید آرایه مرتب شده باشد (پیش فرض صعودی) و سپس
عنصر جستجو شونده با عنصر وسط آرایه مقایسه میشود. اگر برابر بود که جستجو
پایان می پذیرد والا اگر بزرگتر بود، به نیمه ی بالایی آرایه رفته و مجددا
با عنصر وسط آن مقایسه میشود و اگر کوچکتر باشد به نیمه ی پایین آرایه رفته
و با عنصر وسط آن محدوده مقایسه صورت میگیرد. این عمل تا تایید شدن عنصر
مورد نظر یا رسیدن به جایی که دیگر امکان نصف کردن آرایه وجود نداشته باشد،
ادامه می یابد.
عنصر جستجو شونده با عنصر وسط آرایه مقایسه میشود. اگر برابر بود که جستجو
پایان می پذیرد والا اگر بزرگتر بود، به نیمه ی بالایی آرایه رفته و مجددا
با عنصر وسط آن مقایسه میشود و اگر کوچکتر باشد به نیمه ی پایین آرایه رفته
و با عنصر وسط آن محدوده مقایسه صورت میگیرد. این عمل تا تایید شدن عنصر
مورد نظر یا رسیدن به جایی که دیگر امکان نصف کردن آرایه وجود نداشته باشد،
ادامه می یابد.
کد:
int binarySearch(int arr[], int len, int pat)
{
int mid, low=0, high=len-1;
while(low<=high)
{
mid=(low+high)/2;
if(pat<arr[mid])
high=mid-1;
else if(pat>arr[mid])
low=mid+1;
else
return mid;
}
return -1;
}