#include <iostream>
#include <fstream>
void insertionsort (int list[], int n);
int binary_search(int list[], int target, int n);
using namespace std;
int main(void)
{
    int list[100],
        i=0,
        n=0;

    cout << "此程式陣列大小為100，請勿輸入超過100個數\n";
    while(list[i-1] != -1)
    {
        cout << "請輸入陣列(欲要結束請輸入-1):";
        cin >>list[i];
        i++;
        n++;
    }
    n = n-1;
    insertionsort(list,n);
    for(i=0; i<n; i++)
    cout << list[i] << " ";
    cout << "\n";
    system("pause");
    return 0;
}

//Insertionsort use binarysearch
void insertionsort (int list[], int n)
{
    int i,j,x,y;
    for(i=1; i<n; i++)
    {
        x = list[i];
        j = i-1;
        y=binary_search(list, x, i);

        while(j>=y && x<list[j])
        {
            list[j+1] = list[j];
            j--;
        }
        list[j+1] = x;
    }

}

//二分法
int binary_search(int list[], int target, int n)
{
       int bottom=0,
           middle,
           top,
           found=0;
       top = n-1;

       while(!found && bottom <= top)
       {
             middle = (bottom + top)/2;
             if(list[middle] == target)
                found = 1;
             else if(list[middle] > target)
                top = middle-1;
             else
                bottom = middle+1;
       }
       return(middle);
}