#include "stdio.h"
#include "stdlib.h"
#include "time.h"
#define SIZE 10
int linear_search(int array[], int key, int size);
int main(void) {
int rand_array[SIZE];
int i;
int index_num;
srand( time(NULL) );
for ( i=0; i < SIZE; i++ ){
rand_array[i] = ( rand() % 10 ) +1;
printf( "%d ", rand_array[i] );
}
index_num = linear_search(rand_array, 5, SIZE);
printf( "\nThe number you want to search is in index %d ", index_num );
return 0;
}
int linear_search(int array[], int key, int size){
int i;
for( i = 0; i < size; i++){
if ( array[i] == key)
{ return i; }
}
return -1;
}
這是一個搜尋關鍵值(search key)的例子，我們使用 linear_search 函式來實現線性搜尋(linear search )的功能
線性搜尋講白了就是"一個一個從頭找到尾"，用 for 迴圈搭配 if 來進行比較，只要找到符合的值，就直接用 return 交回控制權並且一併將 index 值回傳。
程式的目的在於「搜尋陣列中有沒有關鍵值(search key)出現，以及它位在哪一個 index 上」
有關於 srand、rand 部分是用來幫助產生亂數，在此不多贅述。我們直接看到第 28 行，與之前不同的是我們的輸入引數只有針對一個變數，而在此我們將整個「陣列」當作引入參數。
在函式標頭的地方我們直接表明第一個輸入的參數應該是一個「整數陣列」
氣泡排序
#include "stdio.h"
#define SIZE 10
int main(void) {
const int my_array[SIZE] = { 10,2,9,1,5,6,8,3,7,4 };
int copy_array[SIZE];
int i,set;
int temp;
/* array copy */
for ( i = 0; i < SIZE; i++ ){
copy_array[i] = my_array[i];
}
printf( "Original array : " );
for( i = 0; i < SIZE; i++ ){
printf("%d ",copy_array[i]);
}
/* bubble sort */
for( set = 0; set < (SIZE-1); set++){
for ( i = 0; i < (SIZE-1); i++){
if ( copy_array[i] > copy_array[i+1] )
{
temp = copy_array[i+1];
copy_array[i+1] = copy_array[i];
copy_array[i] = temp;
}
}
}
printf( "\nAfter bubble sort : " );
for( i = 0; i < SIZE; i++ ){
printf("%d ",copy_array[i]);
}
return 0;
}
氣泡排序法為，將一個陣列內的數值按照順序進行排列。其演算法主要為以下
比較第 0 個元素(暫稱為左邊)與第 1 個元素(暫稱為右邊)，把較大的值擺放到右邊
接著比較新的第 1 個元素(暫稱為左邊)與第 2 個元素(暫稱為右邊)，把較大的值擺放到右邊
以此類推，當第一回合執行結束時該陣列中最大的值將被放置在陣列的最右邊，也就是 copy_array[9]。
我們可以看到原本的陣列中，元素 0 是數值 10 。它將在第一次的比較過後被放置到元素 1 的位置，然後再跟元素 2 進行比較。在第二次的比較過後會被放到第 2 個元素的位置。也就是說它就像泡泡一樣不斷的進行比較然後冒出頭來
雖然這個陣列含有 10 個元素，但只需 9 個回合便能將之排序完成，而 1 個回合需要比較 9 次。
二元搜尋
對於小型的陣列或未排序過的陣列而言，線性搜尋可以表現得很好，但是線性搜尋用在大型陣列上就很沒有效率了
若陣列經過排序，則我們可以用速度很快的二元搜尋演算法，此法在每次比較之後，就可以將已排序陣列中一半的元素刪去不考慮
首先，此演算法先找出陣列的中間元素，並且將之與搜尋的關鍵值進行比較。如果相等的話，表示已找到要找的元素，就將此元素的 index 回傳。如果不相等，此時問題便簡化成只需搜尋陣列中的某一半。例如搜尋的關建值小於陣列的中間元素，就搜尋陣列的前半部(假設已排序的陣列由左而右是從小排到大)。
在最壞的情況下用二元搜尋來搜尋具有 1023 個元素的陣列只需要 10 次比較，也就是 2 的次冪 - 1
如果我們需要找 2 的 20 次方 -1 個元素的陣列(1048576個元素)，最多只需要進行 20 次比較。但如果用線性搜尋最糟糕就會需要 1048576 次比較
#include "stdio.h"
int binary_search(const int array[], int search_key, int size);
int main(void) {
setvbuf(stdout,NULL,_IONBF,0);
int my_array[] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 };
int SIZE;
int search_number;
int index;
SIZE = sizeof(my_array)/sizeof(my_array[0]);
printf( "Array size : %d\n", SIZE );
printf("Enter a number : ");
scanf( "%d",&search_number );
index = binary_search( my_array, search_number, SIZE);
if (index != -1){
printf( "\nThe number you want to search(%d) is in index %d",search_number,index );
}
else{
printf( "\nThe number you want to search(%d) not found",search_number);
}
return 0;
}
int binary_search(const int array[], int search_key, int size){
int lowest_index, highest_index;
int middle;
lowest_index = 0;
highest_index = size - 1 ;
while( lowest_index <= highest_index){
middle = (lowest_index + highest_index)/2;
if ( search_key == array[middle] ){
return middle;
}
else if ( search_key > array[middle] ){
lowest_index = middle + 1 ;
}
else{
highest_index = middle - 1 ;
}
}// end while
return -1; // lowest_index == highest_index, means not found.
}
我們在 binary_search 函式裡分別提取出最左側的 index 以及最右側的 index ，接著計算出位於中間的 index 值。
利用不斷的比較 search_key 與陣列中間元素的值，去更改最左側的 index 或是最右側的 index ，並且我們使用一個 while 迴圈不斷的重複執行，最終的結果會收斂使得 search_key 等於陣列中間元素的值，如此一來我們就可以搜尋到我們要的值。
倘若在不斷的遞迴過程中出現 lowest_index > highest_index ，表示在經過多次比較收斂之後發現欲搜尋的 search_number 根本沒有出現在陣列中。
Sizeof 與資料型別
在二元搜尋演算法中我們使用了 sizeof 函數
sizeof 函數會回傳該「型態」(或變數) 佔用了多少個 byte 的記憶體
#include "stdio.h"
int main(void) {
printf("char = %d byte(%d bits)\n", sizeof( char ), sizeof( char ) << 3);
printf("short = %d bytes(%d bits)\n", sizeof( short ), sizeof( short ) << 3);
printf("int = %d bytes(%d bits)\n", sizeof( int ), sizeof( int ) << 3);
printf("long = %d bytes(%d bits)\n", sizeof( long ), sizeof( long ) << 3);
printf("long int = %d bytes(%d bits)\n", sizeof( long int ), sizeof( long int ) << 3);
printf("long long = %d bytes(%d bits)\n", sizeof( long long ), sizeof( long long ) << 3);
printf("\n");
printf("float = %d bytes(%d bits)\n", sizeof( float ), sizeof( float ) << 3);
printf("double = %d bytes(%d bits)\n", sizeof( double ), sizeof( double ) << 3);
printf("\n");
int my_array[] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 };
int sizeofMy_array = sizeof(my_array);
int sizeofMy_array_0 = sizeof(my_array[0]);
int SIZE = sizeof(my_array)/sizeof(my_array[0]);
printf("sizeofMy_array = %d\n", sizeofMy_array);
printf("sizeofMy_array_0 = %d\n", sizeofMy_array_0);
printf("SIZE = %d", SIZE);
return 0;
}
我們運用 sizeof 函數可以知道你的作業系統內部對於這些資料型別各佔了多少的位元組(byte)
例如在我的電腦中 int 型別佔用了 4 bytes ( 1 byte = 8 bits)，但對於一個 16 位元的作業系統來說 int 會佔用 2 bytes
由程式碼的結果中可知
字元
char 1 byte
整數
short 2 bytes
int 4 bytes
long 4 bytes
long int 4 bytes
long long 8 bytes
浮點數
float 4 bytes
double 8 bytes
在二元搜尋中使用的
SIZE = sizeof(my_array)/sizeof(my_array[0]);
是一個很常被使用到的語句，由上述可以得知
sizeof(my_array) 會回傳整個陣列的資料長度
sizeof(my_array[0]) 會回傳陣列中第 0 個元素的資料長度
因陣列的每個元素，資料型態相同(意味著每個元素的資料長度相同)
故 sizeof(my_array)/sizeof(my_array[0]) 會回傳該陣列具有多少個元素
陣列複製
陣列 A 並不能"整個"直接複製為 陣列 B ，若你想要進行陣列的複製，必須一個元素一個元素的進行複製。
#include "stdio.h"
#define SIZE 10
int main(void) {
const int my_array[SIZE] = { 10,2,9,1,5,6,8,3,7,4 };
int copy_array[SIZE];
int i;
copy_array[] = my_array[];
for( i=0; i < SIZE; i++){
printf( "%d", copy_array[i]);
}
return 0;
}
嘗試直接將陣列進行複製是不被允許的。
#include "stdio.h"
#define SIZE 10
int main(void) {
const int my_array[SIZE] = { 10,2,9,1,5,6,8,3,7,4 };
int copy_array[SIZE];
int i;
for ( i=0; i < SIZE; i++ ){
copy_array[i] = my_array[i];
}
for ( i=0; i < SIZE; i++){
printf( "%d ", copy_array[i]);
}
return 0;
}
像這樣將元素一個一個複製，才是正確的作法。
陣列反轉
#include "stdio.h"
#define SIZE 10
void array_inverse(int array[], int size);
int main(void) {
int my_array[SIZE] = { 1,2,3,4,5,6,7,8,9,10 }; /* local */
int i;
printf("Original Array : ");
for ( i=0; i < SIZE; i++){
printf( "%d ", my_array[i]);
}
array_inverse(my_array, SIZE);
printf("\nAfter : ");
for ( i=0; i < SIZE; i++){
printf( "%d ", my_array[i]);
}
return 0;
}
void array_inverse(int array[], int size){
int j;
int temp;
for ( j = 0; j < size/2; j++){
temp = array[j];
array[j] = array[ size-1-j ];
array[ size-1-j ] = temp;
}
}
亂數矩陣
#include "stdio.h"
#include "stdlib.h"
#include "time.h"
#define SIZE 10
int linear_search(int array[], int key, int size);
int main(void) {
int rand_array[SIZE];
int i;
int index_num;
int flag;
srand( time(NULL) );
rand_array[0] = ( rand() % SIZE ) +1;
printf( "%d ", rand_array[0] );
for ( i=1; i < SIZE; i++ ){
flag = 1;
while(flag){
rand_array[i] = ( rand() % SIZE ) +1;
index_num = linear_search(rand_array, rand_array[i], i);
if ( index_num == -1 ) flag = 0;
else flag = 1;
}
printf( "%d ", rand_array[i] );
}
return 0;
}
int linear_search(int array[], int key, int size){
int i;
for( i = 0; i < size; i++){
if ( array[i] == key)
{ return i; }
}
return -1;
}
上述的程式碼則利用了線性搜尋的函式，整個程式的主要目的在於「建立一個 SIZE 大小的亂數矩陣，並且各個元素不得重複」
程式碼中利用 flag 以及 linear_search 來表示是否在 rand_array 中已經有存在相同的值，如果具有相同的值則繼續進行 while 迴圈來蓋過它，如此反覆就一定可以找到不重複的值。
#include "stdio.h"
#include "stdlib.h"
#include "time.h"
#define SIZE 500
int linear_search(int array[], int key, int size);
int main(void) {
int rand_array[SIZE];
int i;
int index_num;
int flag;
srand( time(NULL) );
rand_array[0] = ( rand() % SIZE ) +1;
printf( "%5d", rand_array[0] );
for ( i=1; i < SIZE; i++ ){
flag = 1;
while(flag){
rand_array[i] = ( rand() % SIZE ) +1;
index_num = linear_search(rand_array, rand_array[i], i);
if ( index_num == -1 ) flag = 0;
else flag = 1;
}
if ( i%20 == 0 ) printf("\n");
printf( "%5d", rand_array[i] );
}
return 0;
}
int linear_search(int array[], int key, int size){
int i;
for( i = 0; i < size; i++){
if ( array[i] == key)
{ return i; }
}
return -1;
}
再經過一點改良，我們得到了一個具有 1~500 的亂數矩陣，且彼此的值不重複。
