برنامه: پیدا کردن یک عدد در آرایه به روش دودویی یا 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.");
}
}
}
|
عضو شوید
عضویت سریع
آمار مطالب
آمار بازدید
