جستجوی دودویی یا Binary Search در پایتون

الگوریتم جستجوی دودویی (به انگلیسی: Binary Search)، تکنیکی است برای یافتن یک مقدار عددی از میان مجموعه‌ای از اعداد مرتب. این متد محدودهٔ جستجو را در هر مرحله به نصف کاهش می‌دهد، بنابراین هدف مورد نظر یا به زودی پیدا می‌شود یا مشخص می‌شود که مقدار مورد جستجو در فهرست وجود ندارد.

جستجوی دودویی فقط در آرایه‌های مرتب استفاده می‌شود. در این روش عنصر مورد نظر با خانه وسط آرایه مقایسه می‌شود اگر با این خانه برابر بود جستجو تمام می‌شود اگر عنصر مورد جستجو از خانه وسط بزرگتر بود جستجو در بخش بالایی آرایه و در غیر این صورت جستجو در بخش پایینی آرایه انجام می‌شود (فرض کرده‌ایم آرایه به صورت صعودی مرتب شده‌است) این رویه تا یافتن عنصر مورد نظر یا بررسی کل خانه‌های آرایه ادامه می‌یابد.

کد جستجوی دودویی در پایتون به این صورت که ابتدا ما یک آرایه تعریف میکنیم و آرایه خود را مرتب میکنیم. بعد از مرتب کردن متد جستجوی دودویی در پایتون را صدا میزنیم تا عدد مورد نظر را پیدا کند.

 

سورس کد جستجوی دودویی در C++ :


#include 
 
void main(){
clrscr();
	       int array[5]={12 , 34 , 3 ,10 , 13} , number = 121 , i ,j , temp;
 
	       for(i=0 ; i< 5 ; i++){
		  for(j=0 ; j< 4 ; j++){
		    if(array[j] > array[j+1]){
		      temp =array[j];
		      array[j]= array[j+1];
		      array[j+1] = temp;
 
		    }
		  }
	       }
 
	       for(i=0 ; i<5 ; i++){
		   cout<<array[i]<<"  ";
	       }
 
	       //----------Search----------------------
	       int start = 0 , end = 4 , mid;
 
	       while(start <= end){
 
		mid = (start + end ) / 2 ;
		if(array[mid] == number){
		   cout<<"\n Found :"<<array[mid];
		   break ;
		}
 
		if(number < array[mid]){
		     end = mid -1 ;
		}else if( number > array[mid]){
		    start = mid + 1;
		 }
 
	       }
 
	      if(start > end ){
		  cout<<"\n Number Not Found !!!!!!!";
	      }
 
getch();
}

سورس کد جستجو باینری در زبان پایتون :


def binarySearch(list1,item):
    first=0
    last=len(list1)-1
    found=False

    while first <= last and not found :
        mid=int((first+last)/2)
        if list1[mid] == item :
            found= True
            break
        else :
            if item < list1[mid] :
                last=mid-1
            else :
                first=mid+1
    if found ==True :
        rsult='{} position in List : {}'.format(found,mid)
    else :
        rsult= 'not found !!'
    return rsult

Mlist = [0, 1, 2, 8, 13, 17, 19, 32, 42]
while True:
    print('Main List: ', Mlist)
    
    k = input ('enter Number to search ( x for Exit) :')
    if k == 'x' or k =='X':
        break
    
    print('\n',binarySearch(Mlist, int(k)))
    print('-----------------------------------------------')

 

شما میتوانید این پروژه را به صورت کامل از پایـ سافت دریافت کنید

  قیمت 20هزار تومن  

برای اطلاعات بیشتر و خرید لطفا به آیدی زیر در تلگرام پیام دهید

@Khorammfar

شماره تماس : 09374851282