access_time۵ فروردین, ۱۳۹۹
perm_identity ارسال شده توسط شاه‌کد
visibility 562 بازدید
ساده ترین روش برای جستجو در آرایه استفاده از جستجوی خطی است. جستجوی خطی به صورت زیر عمل میکند:
- از اولین عنصر آرایه شروع میکند و یکی یکی عناصر آرایه را با مقدار جستجو شده مقایسه میکند.
- اگر یکی از عناصر با مقدار جستجو شده برابر بود،ایندکس آن عنصر را برمیگرداند و جستجو متوقف میشود.
- اگر تا آخر آرایه عنصر مشابهی پیدا نشد مقدار ۱- را برمیگرداند.
فرض کنید که ما می خواهیم حروف “J” را پیدا کنیم که در اینجا کد به زبان ++c و جاوا را در اختیار شما قرار دادیم.
کد جستجوی خطی به زبان ++C:
#include <iostream>
using namespace std;
int search(int arr[], int n, int x)
{
int i;
for (i = 0; i < n; i++)
if (arr[i] == x)
return i;
return -1;
}
int main(void)
{
int arr[] = { 2, 3, 4, 10, 40 };
int x = 10;
int n = sizeof(arr) / sizeof(arr[0]);
int result = search(arr, n, x);
(result == -1)? cout<<"Element is not present in array"
: cout<<"Element is present at index " <<result;
return 0;
}کد جستجوی خطی به زبان جاوا:
public static int search(int arr[], int x)
{
int n = arr.length;
for(int i = 0; i < n; i++)
{
if(arr[i] == x)
return i;
}
return -1;
}
public static void main(String args[])
{
int arr[] = { 2, 3, 4, 10, 40 };
int x = 10;
int result = search(arr, x);
if(result == -1)
System.out.print("Element is not present in array");
else
System.out.print("Element is present at index " + result);
}نکات مهم:
این الگوریتم به ندرت مورد استفاده قرار میگیرد زیرا الگوریتم های جستجوی دیگر مانند جستجوی دودویی اجازه میدهند مقایسه سریعتری نسبت به جستجوی خطی داشته باشیم.
مرتبه زمانی: مرتبه زمانی جستجوی خطی O(n) است.