جست و جوی دودویی

برنامه: پیدا کردن یک عدد در آرایه به روش دودویی یا Binary Search  

الگوریتم:

ابتدا آرایه ی ورودی را توسط یکی از روش های مرتب سازی (به عنوان مثال مرتب سازی حبابی یا Buble Sort)  که قبلا نوشته ایم ،مرتب کرده سپس با دستورات زید به جست و جو می پردازیم

 

int binary_search(int arr[],int arrsize,int obj)
{
     int first = 0;
     int last = arrsize;
     int middle = (first + last) / 2;

      while(last >= first)
      {
             if(arr[middle] == obj)
             {
                               return middle;
             }
              else if(arr[middle] > obj)
                     {
                            last = middle-1;
                            middle = (first + last) / 2;
                       }else
                              {
                                       first = middle+1;
                                       middle = (first + last) / 2;
                               }
           }
return -1;
}

ورودی ها عبارتند از: 

1 - یک آرایه (مرتب شده به صورت صعودی). (اگر آرایه نزولی مرتب شده باید جای ">"  ,  "<" را عوض کنیم)

2 - اندازه ی آرایه

3 - و عددی که باید دنباله آن بگردیم.

 

که در صورت پیدا کردن عدد در آرایه عنصر، اندیس آن و در غیر اینصورت عدد منفی یک ( 1- ) را بر می گرداند.

 

* نکات مربوط به کد سی شارپ و جاوااسکریپت

تکست باکس اول  آرایه ی ورودی را با این فرمت که پس از هر عدد یک " , " باشد(بدون هیچ فاصله ای) را گرفته و در تکست باکس دوم عددی را که باید به دنبال آن بگریم  از ورودی می گیریم.

 برنامه ی جست و جوی دودویی به زبان ++C

 //Writed By barnamenevisi-ccj.mihanblog.com

#include
#include

#define size 10
//--------------------------Buble Sort-------------------------------
void bubleSort(int num[],int numSize)
{
   int temp=0;
   for(int i=numSize;i>0;i--)
   {
           for(int j=0;j<i;j++)
                 if(num[j] > num[j+1])
                 {
                            temp = num[j];
                            num[j] = num[j+1];
                            num[j+1] = temp;
                  }
   }

}
//-----------------------Binary Search-------------------------------------
int binary_search(int arr[],int arrsize,int obj)
{
   int first = 0;
   int last = arrsize;
   int middle = (first + last) / 2;

   while(last >= first)
   {
           if(arr[middle] == obj)
           {
                     return middle;
            }
            else if(arr[middle] > obj)
                   {
                           last = middle-1;
                           middle = (first + last) / 2;
                   }else
                          {
                                first = middle+1;
                                middle = (first + last) / 2;
                           }
   }
return -1;
}
//--------------------------Main ------------------------------------
main()
{

   int test[size]={10,19,12,18,15,17,11,14,13,16};
   int searchobj=0;
   int flag;

   //sort array
   bubleSort(test,size-1);

   cout<<"Enter number to search : ";
   cin>>searchobj;

   flag = binary_search(test,size-1,searchobj);

   if(flag != -1)
                    cout<<"\nfind item in element "<<flag+1<<" .";
   else         cout<<"\nnot found.";

getch();
return 0;
}

 

   برنامه ی جست و جوی دودویی به زبان #C 

 using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;

namespace WindowsFormsApplication1
{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}
//-----------------------Binary Search-------------------------------------
int binary_search(int[] arr, int arrsize, int obj)
{
   int first = 0;
   int last = arrsize;
   int middle = (first + last) / 2;

   while(last >= first)
   {
            if(arr[middle] == obj)
            {
                     return middle;
             }
            else if(arr[middle] > obj)
                   { 
                             last = middle-1;
                             middle = (first + last) / 2;
                   }else{
                                 first = middle+1;
                                 middle = (first + last) / 2;
                            }
    }
return -1;
}
//.............................Buble Sort........................................
int[] bubleSort(string test)
{
   int i = 0;
   int test2size = 0;

   for (i = 0; i < txt1.TextLength; i++)
         if (test[i] == ',')
               test2size++;

    int[] test2 = new int[test2size];
   test2size = 0;

    for (i = 0; i < txt1.TextLength; i++)
   {

        if (test[i] != ',')
                 test2[test2size] = test2[test2size] * 10 + Int32.Parse(test[i].ToString());
        else test2size++;

   }
   //sorting by buble sort algorithm
   int temp = 0;
   for (i = test2size - 1; i > 0; i--)
   {
             for (int j = 0; j < i; j++)
                      if (test2[j] > test2[j + 1])
                      {
                                 temp = test2[j];
                                 test2[j] = test2[j + 1];
                                 test2[j + 1] = temp;
                       }
   }

return test2;

}
private void button1_Click(object sender, EventArgs e)
{
   int flag;
   int[] test = bubleSort(txt1.Text);

   flag = binary_search(test, test.Length, Int32.Parse(txt2.Text));
   if (flag != -1)
   {
                 MessageBox.Show("Find item on element " + (flag + 1) + " .");
   }
   else MessageBox.Show("Not Found.");

}
}
}