//#include <stdio.h>             // c 库
#include <stdlib.h>                //maclloc 库
#include <iostream>                // c++ 库

// 有本句 ，下面cout 前面可以没有  std::
using namespace std;
typedef int   Elem;
#define MAXSIZE 11


typedef struct {
	Elem data[MAXSIZE];
	int len;
} SqQueue;

void InitSq(SqQueue& T) {
	for (int i = MAXSIZE; i > 0; i--)
		T.data[i] = i;
	//T.data[] = { 1,2,3,4,5,6,7,8,9,10,11 };
}

void TravSq(SqQueue T) {
	for (int i = MAXSIZE; i > 0; i--)
		cout << T.data[i] << " ";

}

// 顺序查找
//巧妙设置哨兵：待查值存入数组0， 一定能查找到，不会越界（一定能查到，最坏返回0）
int SSserch(SqQueue T, Elem x) {
	int i;
	T.data[0] = x;
	for (i = MAXSIZE; T.data[i] != x; i--)
		;
	return i;

}

//二分查找
//设置下查找上下限，待查key与中间值比：若等，查找成功；或key小，上限缩小；反之，下限增大；
int BIserch(SqQueue T, Elem x) {
	int low = 1, high = MAXSIZE, mid;
	while (low <= high) {
		mid = (low + high) / 2;
		if (T.data[mid] == x)
			return mid;
		else if (T.data[mid] > x)
			high = mid-1;
		else low = mid+1;
	}

	return 0;
}


void main() {

	SqQueue T;
	InitSq(T);
	//TravSq(T);

	// 顺序查找
	//cout << " SSserch is  " << SSserch(T, 11);

	// 二分查找
	cout << " BIserch is  " << BIserch(T, 11);
}