Dizilerde arama yapmak

DİZİLERDE ARAMA YAPMAK

Programcı sıklıkla, dizilerde tutulan büyük miktarlarda veri ile çalışacaktır. Bir dizinin, belli bir arama değerine eşit olan bir değer içerip içermediğine karar vermek gerekebilir. Dizinin belirli bir elemanını bulma sürecine arama denir. Bu kısımda iki arama tekniğini (basit lineer arama ve daha karmaşık olan ikili arama teknikleri) anlatacağız. Bu ünitenin sonundaki alıştırma 6.34 ve 6.35'te bu iki tekniğin yinelemeli versiyonlarını soracağız.

Lineer arama (Şekil 6.18), dizinin her elemanını arama değeriyle karşılaştırmaktadır. Dizi herhangi bir şekilde sıralanmadığından değer ilk ya da son elemanda bulunabilir. Bu sebepten, program ortalama olarak, arama değeriyle dizinin elemanlarının yarısını karşılaştırmalıdır.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

/* Şekil 6.18: fig06_18.c
Dizide lineer arama yapmak */
#include <stdio.h>
#define BOYUT 100
 
int lineerArama( const int [], int, int );
 
int main( )
{
int a[ BOYUT ], x, aramaDegeri, eleman;
 
 for ( x = 0; x <= BOYUT - 1; x++ ) /* veri oluştur */
     a[ x ] = 2 * x;
 
printf( "Arama değeri tamsayısını gir:\n" );
scanf( "%d", & aramaDegeri);
eleman = lineerArama( a, aramaDegeri, BOYUT);
 
  if ( eleman != -1 )
      printf( "Bu değer, eleman %d de bulundu\n", eleman );
  else
      printf( "Bu değer bulunamadı\n" );
 
return 0;
}
 
int lineerArama( const int dizi[], int anahtar, int boyut )
{
int n;
 
  for ( n = 0; n <= boyut - 1; ++n )
      if ( dizi[ n ] == anahtar )
          return n;
 
  return -1;
}

Arama değeri tamsayısını gir:
36
Değer,eleman 18 de bulundu

Arama değeri tamsayısını gir:
37
Değer bulunamadı

Şekil 6.18 Dizide lineer arama yapmak

Lineer arama , küçük ya da sıralanmamış dizilerde iyi bir şekilde çalışır. Ancak büyük diziler için lineer arama yetersiz kalmaktadır. Eğer dizi sıralanmışsa, daha hızlı olan ikili arama tekniği kullanılabilir.

İkili arama tekniği, her karşılaştırmadan sonra sıralanmış bir dizideki elemanların yarısını elemektedir. Algoritma, dizinin ortadaki elemanını bulmakta ve bu elemanın değerini arama değeriyle karşılaştırmaktadır. Eğer ikisi eşitse, arama değeri bulunmuştur ve o elemanın dizi belirteci geri döndürülür. Eğer bu iki değer eşit değilse, problem dizinin yarısını aramaya indirgenmiştir. Eğer arama değeri dizinin ortadaki elemanından daha küçükse, dizinin ilk yarısı aranır. Aksi takdirde ise dizinin ikinci yarısı aranır. Eğer arama değeri belirlenen alt dizide de (orijinal dizinin bir parçası) bulunamazsa, algoritma orijinal dizinin dörtte birinde tekrarlanır. Arama, alt dizilerden birinin ortadaki elemanıyla arama değeri eşit olunca ya da alt dizi arama değerine eşit olmayan tek bir elemana sahip oluncaya dek (yani arama değeri bulunamayıncaya dek) devam eder.

En kötü durumda ikili arama, 1024 elemanlı bir dizide arama yaparken en fazla 10 karşılaştırma yapacaktır.1024'ü sürekli olarak ikiye bölmek 512,256,128,64,32,16,8,4,2 ve 1 değerlerini verir. 1024 ( 210 ) sayısı 1 değerini elde etmek için ikiye 10 kez bölünmüştür. 2'ye bölmek, ikili aramada bir karşılaştırma yapmak ile eşdeğerdir. 1048576 ( 220 ) elemanlı bir dizide arama değerini bulmak en fazla 20 karşılaştırma gerektirmektedir. Bir milyar eleman içeren bir dizide arama değerini bulmak için en fazla 30 karşılaştırma yapılmalıdır. Bu, arama değerini bulabilmek için ortalama olarak dizinin elemanlarının yarısıyla karşılaştırma yapan lineer aramaya göre performansta olağanüstü bir artış demektir. Bir milyar elemana sahip bir dizide, bu fark 500 milyon karşılaştırma ile 30 karşılaştırma arasındadır! Bir dizi için yapılacak en fazla karşılaştırma, 2'nin dizideki eleman sayısından büyük ilk üssü ile bulunabilir.

Şekil 6.19, ikiliArama fonksiyonunun tekrarlı versiyonunu göstermektedir. Fonksiyon (32.satırda tanımlanmıştır) 4 argüman almaktadır. Bunlar ; b tamsayı dizisi, bir tamsayı olan aramaDegeri, dizinin en düşük belirtecini gösteren enAlt ve dizinin en büyük belirtecini gösteren enUst olarak belirlenmiştir. Eğer arama değeri bir alt dizinin ortadaki elemanıyla eşleşmezse, enAlt ya da enUst argümanı daha küçük bir alt dizide aramanın devam edebilmesi için değiştirilir. Eğer arama değeri ortadaki elemandan küçükse, enUst belirteci orta-1 olacak biçimde değiştirilir ve arama, enAlt belirteci ile orta-1 arasındaki elemanlarda devam ettirilir. Eğer arama değeri ortadaki elemandan daha büyükse, enAlt belirteci orta+1 olacak hale getirilir ve arama, orta+1 ile enUst arasındaki elemanlarda devam ettirilir. Program 15 elemanlı bir dizi kullanmaktadır. 2'nin dizi elemanı sayısından büyük ilk üssü 16 (24) olduğundan arama değerini bulmak için en fazla 4 arama yapmak gerekmektedir. Program, baslikYazdir fonksiyonu (54.satır) ile dizi belirteçlerini yazdırmakta ve satirYazdir fonksiyonu (73.satır) ile ikili arama sürecindeki her alt diziyi yazdırmaktadır. Her alt dizideki orta eleman, arama değeriyle karşılaştırılan değeri göstermek için bir yıldız karakteri (*) ile belirtilmiştir.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

/* Şekil 6.19: fig06_19.c
Bir dizide ikili arama */
#include <stdio.h>
#define BOYUT 15
 
int ikiliArama( const int [ ], int, int, int );
void baslikYazdir( void );
void satirYazdir( const int [], int, int, int );
 
int main( )
{
int a[BOYUT], i, anahtar, sonuc;
 
  for ( i = 0; i <= BOYUT - 1; i++ )
      a[ i ] = 2 * i;
 
printf( "0 ile 28 arasında bir sayı giriniz: " );
scanf( "%d", & anahtar );
 
baslikYazdir ( );
sonuc = ikiliArama ( a, anahtar, 0, BOYUT - 1 );
 
  if (sonuc!= -1 )
     printf("\n%d,eleman %d içinde bulundu\n",anahtar,sonuc);
  else
      printf( "\n%d bulunamadı\n", anahtar);
 
return 0;
}
 
int ikiliArama(const int b[],int aramaDegeri,int enAlt,int enUst)
{
int orta;
 
  while (enAlt<= enUst) {
      orta = ( enAlt + enUst ) / 2;
      satirYazdir ( b, enAlt, orta, enUst);
        if (aramaDegeri == b[orta] )
            return orta;
        else if (aramaDegeri < b[orta] )
            enUst = orta - 1;
        else
            enAlt = orta + 1;
  }
 
return -1; /* aramaDegeri bulunamadı */
}
 
/* Çıkış için bir başlık yazdır */
void baslikYazdir ( void )
{
int i;
 
printf( "\nBelirteçler:\n" );
 
  for ( i = 0; i <= BOYUT - 1; i++ )
      printf( "%3d ", i );
 
printf( "\n" );
 
  for ( i = 1; i <= 4 * BOYUT; i++ )
      printf( "-" );
 
printf( "\n" );
}
 
/* Dizinin işlem yapılan kısmını gösteren bir
satır çıktı yazdır. */
void satirYazdir ( const int b[], int enAlt, int orta, int enUst)
{
int i;
 
  for ( i = 0; i <= BOYUT - 1; i++ )
      if ( i < enAlt || i > enUst)
          printf( " " );
      else if ( i == orta)
          printf("%3d*",b[i]);/*ortadaki değeri işaretle */
      else
          printf( "%3d ", b[ i ] );
 
printf( "\n" );
}

0 ile 28 arasında bir sayı giriniz: 25

Belirteçler:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
0 2 4 6 8 10 12 14* 16 18 20 22 24 26 28
16 18 20 22* 24 26 28
24 26* 28
24*
25 bulunamadı

0 ile 28 arasında bir sayı giriniz: 8

Belirteçler:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
0 2 4 6 8 10 12 14* 16 18 20 22 24 26 28
0 2 4 6* 8 10 12
8 10* 12
8*
8, dizi elemanı 4 içinde bulundu

0 ile 28 arasında bir sayı giriniz: 8

Belirteçler:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
0 2 4 6 8 10 12 14* 16 18 20 22 24 26 28
0 2 4 6* 8 10 12

6, dizi elemanı 3 içinde bulundu

Şekil 6.19 Sıralı bir dizi için ikili arama