برنامه جاوا برای جستجوی خطی
در دنیای علوم کامپیوتر ، جستجوی الگوریتم های تکنیک های اساسی برای بازیابی اطلاعات از ساختارهای داده است. یکی از ساده ترین و بصری ترین الگوریتم های جستجو ، جستجوی خطی است. از جستجوی خطی برای جستجوی یک عنصر کلیدی از چندین عنصر استفاده می شود. جستجوی خطی امروز کمتر مورد استفاده قرار می گیرد زیرا کندتر از جستجوی باینری و هشدار است.
جستجوی خطی ، همچنین به عنوان جستجوی متوالی شناخته می شود ، روشی ساده برای یافتن یک عنصر در یک لیست است. این هر عنصر از لیست را به صورت متوالی بررسی می کند تا زمانی که یک مسابقه پیدا کند یا به پایان لیست برسد. این روش به بهترین وجه برای مجموعه داده های کوچک یا غیرمجاز مناسب است که در آن سربار الگوریتم های پیچیده تر توجیه نمی شود.
الگوریتم برای جستجوی خطی
مرحله 1: از آرایه عبور کنید.
مرحله 2: عنصر کلید را با عنصر آرایه مطابقت دهید.
مرحله 3: در صورت یافتن عنصر کلید ، موقعیت شاخص عنصر آرایه را برگردانید.
مرحله 4: اگر عنصر کلیدی یافت نشد ، بازگشت -1.
public class LinearSearchExample{
public static int linearSearch(int[] arr, int key){
for(int i=0;i
خروجی:
50 در فهرست یافت می شود: 3
مزایا
سادگی: درک و اجرای آن آسان است.
بدون پردازش: نیازی به مرتب سازی داده ها نیست.
تطبیق پذیری: می توان در هر نوع ساختار داده (آرایه ها ، لیست های مرتبط و غیره) استفاده کرد.
معایب
ناکارآمدی: به طور متوسط ، نیاز به بررسی نیمی از عناصر (O (N/2)) و در بدترین حالت ، همه عناصر (O (n)) است.
برای مجموعه داده های بزرگ مناسب نیست: با افزایش اندازه مجموعه داده ها غیر عملی می شود.
تجزیه و تحلیل عملکرد
پیچیدگی زمانی
پیچیدگی زمان جستجوی خطی o (n) است ، جایی که n تعداد عناصر موجود در آرایه است. از آنجا که در بدترین حالت ، الگوریتم باید هر عنصر را یک بار بررسی کند.
پیچیدگی فضا
پیچیدگی فضا o (1) است زیرا الگوریتم صرف نظر از اندازه ورودی از مقدار ثابت فضای اضافی استفاده می کند.
بهترین مورد
بهترین پیچیدگی زمان بهترین حالت O (1) است که وقتی عنصر هدف در موقعیت اول در آرایه قرار می گیرد ، رخ می دهد.
مرجع: https: //www.tpointtech.com/linear-search-in-java
برنامه:
package afterfeb13;
public class linearsearch {
public static void main(String[] args) {
int[]score= {80,90,70,77,66,55,88,99,102,150};
int key=150;
for(int i=0;i
خروجی: کلید 150 موجود در فهرست 9
جستجوی دودویی در جاوا
جستجوی باینری یکی از تکنیک های جستجو است که هنگام طبقه بندی ورودی در اینجا ، ما روی پیدا کردن عنصر میانی که به عنوان یک قاب مرجع عمل می کند ، چه به سمت چپ یا راست به آن عمل می کند ، تمرکز می کنیم زیرا عناصر در حال حاضر مرتب شده اند. این جستجو به بهینه سازی تکنیک جستجو با هر تکرار به جستجوی باینری کمک می کند و خوانندگان بر آن استرس می کنند زیرا به طور غیرمستقیم در حل سوالات اعمال می شود.
الگوریتم جستجوی دودویی در جاوا
در زیر الگوریتم طراحی شده برای جستجوی باینری:
1. راه اندازی
2. آرایه ورودی و هدف را هدف قرار دهید
3.Initialise start = 0 و پایان = (اندازه آرایه -1)
4. متغیر میانی
5.Mid = (شروع+پایان)/2
6. اگر آرایه[ mid ] == هدف سپس اواسط بازگشت
7. در آرایه[ mid ] <هدف سپس شروع = اواسط+1
8. در صورت آرایه[ mid ] > هدف سپس پایان = اواسط 1
9. در صورت شروع <= پایان سپس مرحله 5
10.Return -1 همانطور که عنصر یافت نشد
11.Exit
مرجع: https: //www.geeksforgeeks.org/binary-search-in-java/
برنامه withoutretunr سابق
package afterfeb13;
public class binarysearch {
public static void main(String[] args) {
int[] days = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };
int key = 14;// this for num less--->3
int min_index = 0;
int max_index = days.length - 1;
while (min_index <= max_index) {
int mid_index = (min_index + max_index) / 2;// 0+14/2=7 //8+14/2=23/2= 11 //12+14/2---26/2 =13
// this for num less---> 0+14/2=7//0+6/2=3//0+1/2=0.5==1
if (days[mid_index] == key) // indx=7 num 8==15 //indx=11 num 12==15// indx=14 num 15
// this for num less--->if nu less indx=7 num 8==3 //4==3//2==3//
{
System.out.println("key " + key + " is present at position " + mid_index);
break;
} else if (key > days[mid_index])// 15>8//15>11 //15>12
{
min_index = mid_index + 1;// 7+1//11+1
// this for num less--->1+1=2
}
else //
{
max_index = mid_index - 1;// this for num less---> 7-1//2-1
}
}
if (min_index > max_index)
System.out.println("search key not found");
}
}
خروجی:
کلید 14 در موقعیت 13 وجود دارد
