作業14

/*
作業十四：二分搜尋法程式。

        輸入五筆資料，5.10.15.20.25，用陣列儲孀起來

然後輸入搜尋的值為5 ，25，17，使用二分搜尋法程式，完成搜尋的工作。第一次搜尋的值為5，
所以主程式呼叫二元搜尋法副程式，判斷搜尋值怯否再這個陣列裡面的哪一個元素

第二次搜尋的值為25，所以主程式呼叫二元搜尋法副程式，判斷搜尋值怯否再這個陣列裡面的哪一個元素

第三次搜尋的值為17，所以主程式呼叫二元搜尋法副程式，判斷搜尋值怯否再這個陣列裡面的哪一個元素

列印出每次搜尋這個陣列裡面的哪一個元素。如果找不到的話就印出找不到資料
------------------------------
1.先將陣列排序過 
2.搜尋　 
*/

#include <stdio.h>
#include <stdlib.h>


//排序陣列用 （交換用函數） 
void swap(int *a, int *b)
{ 
  int t=*a; *a=*b; *b=t; 
}

//快速排序法 
void sort(int arr[], int beg, int end) 
{
  if (end > beg + 1) 
  {int piv = arr[beg], k = beg + 1, r = end;
    
    while (k < r) 
    {
      if (arr[k] <= piv) 
        k++;
      else 
        swap(&arr[k], &arr[--r]);
    }
    swap(&arr[--k], &arr[beg]);
    sort(arr, beg, k);
    sort(arr, r, end);
  }
}

int binarysearch(int[], int, int);
int binarysearch(int data[],int search,int n)
{
    int low = 0, high = n - 1;

    while (low <= high)
    {
        int mid = (low + high) / 2;

        if (data[mid] == search)
        {
            return mid;
        }
        else if (data[mid] > search)
        {
            high = mid - 1;//往上找 
        }
        else if (data[mid] < search)
        {
            low = mid + 1;//往下找 
        }
    }

    return -1;//找不到 
}
int main(void)
{   
    printf("四資工一甲　歐陽毅\n"); 
    printf("作業14\n\n");
    int search, ans;
    int data[] = {5, 10, 15, 20, 25};
    sort(data,0,4);//先將陣列排序過（假如沒排序的話） 
    printf("請輸入欲搜尋的資料: ");
    scanf("%d", &search);

    // 呼叫函式進行搜尋
    ans = binarysearch(data, search, sizeof(data) / sizeof(int));

    if (ans < 0)
    {
        printf("找不到 %d\n", search);
    }
    else
    {
        printf("在第 %d 筆資料找到 %d\n", ans + 1, search);
    }

    system("pause");
}