Terkadang kita perlu menemukan nilai-nilai tertentu dalam sebuah array yang memiliki jumlah data yang sangat banyak. Teknik untuk mencari nilai-nilai tersebut dinamakan 'searching'.
Ada 2 macam teknik searching yang akan dijelaskan dalam post ini. Yaitu 'linear search' dan 'binary search'.
- Linear search
Linear search membandingkan semua elemen yang ada dengan search key (nilai yang dicari). Karena nilai-nilai dalam array tidak selalu harus urut, maka hasil bisa ditemukan di bagian manapun.
Berikut contoh program untuk linear search:
/* Fig. 6.18: fig06_18.c
Linear search of an array */
#include <stdio.h>
#define SIZE 100
/* function prototype */
int linearSearch( const int array[], int key, int size );
/* function main begins program execution */
int main( void )
{
int a[ SIZE ]; /* create array a */
int x; /* counter for initializing elements 0-99 of array a */
int searchKey; /* value to locate in array a */
int element; /* variable to hold location of searchKey or -1 */
/* create data */
for ( x = 0; x < SIZE; x++ ) {
a[ x ] = 2 * x;
} /* end for */
printf( "Enter integer search key:\n" );
scanf( "%d", &searchKey );
/* attempt to locate searchKey in array a */
element = linearSearch( a, searchKey, SIZE );
/* display results */
if ( element != -1 ) {
printf( "Found value in element %d\n", element );
} /* end if */
else {
printf( "Value not found\n" );
} /* end else */
getch ();
} /* end main */
/* compare key to every element of array until the location is found
or until the end of array is reached; return subscript of element
if key or -1 if key is not found */
int linearSearch( const int array[], int key, int size )
{
int n; /* counter */
/* loop through array */
for ( n = 0; n < size; ++n ) {
if ( array[ n ] == key ) {
return n; /* return location of key */
} /* end if */
} /* end for */
return -1; /* key not found */
} /* end function linearSearch */
Berikut hasil output:
-Binary search
Linear search hanya bisa bekerja dengan baik pada data yang sedikit dan tidak urut. Namun untuk data-data yang banyak dan terurut, teknik binary search sangat cocok untuk digunakan.
Binary search bekerja dengan cara membandingkan nilai data yang ada di bagian tengah dengan nilai yang dicari. Bila nilai data yang ada di tengah tersebut sama dengan nilai yang dicari,maka data berhasil ditemukan. Namun bila tidak, data akan membandingkan apakah nilai tengah itu lebih besar dari nilai yang dicari atau lebih kecil. Bila lebih besar, maka progrm akan mengulang langkah yang sama hanya pada data-data setelah nilai tengah. Sebaliknya bila nilai tengah lebih kecil, maka program akan mengulang langkah yang sama pada data sebelum nilai tengah tersebut.
Berikut contoh program binary search:
/* Fig. 6.19: fig06_19.c
Binary search of a sorted array */
#include <stdio.h>
#define SIZE 15
/* function prototypes */
int binarySearch( const int b[], int searchKey, int low, int high );
void printHeader( void );
void printRow( const int b[], int low, int mid, int high );
/* function main begins program execution */
int main( void )
{
int a[ SIZE ]; /* create array a */
int i; /* counter for initializing elements 0-14 of array a */
int key; /* value to locate in array a */
int result; /* variable to hold location of key or -1 */
/* create data */
for ( i = 0; i < SIZE; i++ ) {
a[ i ] = 2 * i;
} /* end for */
printf( "Enter a number between 0 and 28: " );
scanf( "%d", &key );
printHeader();
/* search for key in array a */
result = binarySearch( a, key, 0, SIZE - 1 );
/* display results */
if ( result != -1 ) {
printf( "\n%d found in array element %d\n", key, result );
} /* end if */
else {
printf( "\n%d not found\n", key );
} /* end else */
getch();
return 0; /* indicates successful termination */
} /* end main */
/* function to perform binary search of an array */
int binarySearch( const int b[], int searchKey, int low, int high )
{
int middle; /* variable to hold middle element of array */
/* loop until low subscript is greater than high subscript */
while ( low <= high ) {
/* determine middle element of subarray being searched */
middle = ( low + high ) / 2;
/* display subarray used in this loop iteration */
printRow( b, low, middle, high );
/* if searchKey matched middle element, return middle */
if ( searchKey == b[ middle ] ) {
return middle;
} /* end if */
/* if searchKey less than middle element, set new high */
else if ( searchKey < b[ middle ] ) {
high = middle - 1; /* search low end of array */
} /* end else if */
/* if searchKey greater than middle element, set new low */
else {
low = middle + 1; /* search high end of array */
} /* end else */
} /* end while */
return -1; /* searchKey not found */
} /* end function binarySearch */
/* Print a header for the output */
void printHeader( void )
{
int i; /* counter */
printf( "\nSubscripts:\n" );
/* output column head */
for ( i = 0; i < SIZE; i++ ) {
printf( "%3d ", i );
} /* end for */
printf( "\n" ); /* start new line of output */
/* output line of - characters */
for ( i = 1; i <= 4 * SIZE; i++ ) {
printf( "-" );
} /* end for */
printf( "\n" ); /* start new line of output */
} /* end function printHeader */
/* Print one row of output showing the current
99 part of the array being processed. */
void printRow( const int b[], int low, int mid, int high )
{
int i; /* counter for iterating through array b */
/* loop through entire array */
for ( i = 0; i < SIZE; i++ ) {
/* display spaces if outside current subarray range */
if ( i < low || i > high ) {
printf( " " );
} /* end if */
else if ( i == mid ) { /* display middle element */
printf( "%3d*", b[ i ] ); /* mark middle value */
} /* end else if */
else { /* display other elements in subarray */
printf( "%3d ", b[ i ] );
} /* end else */
} /* end for */
printf( "\n" ); /* start new line of output */
} /* end function printRow */
Hasil output:
Tidak ada komentar:
Posting Komentar