#include "pch.h"
#include <iostream>
using namespace std;
//折半查找
int BinarySearchFunc(int key, int a[], int n)
{
  int low, mid, high;   //查找标记
  int count = 0;      //统计查找次数
  low = 0;
  high = n - 1;
  int countT = 0;
  while (low <= high)
  {
    count++;
    mid = (high + low) / 2;
    if (key == a[mid])
    {
      cout << "查找成功，位置查找次数为：" << count << "对应的位置是：a[" << mid << "]" << endl;
      countT++;
      break;
    }
    else if (key < a[mid])  //查找数据是在low-mid之间
    {
      high = mid - 1;
    }
    else if (key > a[mid])  //查找数据是在mid-high之间
    {
      low = mid + 1;
    }
  }
  if (countT == 0)
  {
    cout << "查找key失败！" << endl;
  }
  return 0;
}
int main()
{
  cout << "折半查找：" << endl;
  int key;
  int array[10] = { 1,2,13,34,45,56,78,79,88,92 };
  cout << "请输入要查找的数据：";
  cin >> key;
  BinarySearchFunc(key, array, 10);
  return 0;
}
哈希表
//#define N  11
//#define L  13
//
//int Data[N] = { 10,23,33,26,56,11,88,56,66,22,74 }; //原始表
//int Hash[L] = { 0 };                //哈希表
//
//创建使用哈希表
//void CreateHash()
//{
//  for (int i = 0; i < N; i++)
//  {
//    int j=Data[i] % L;  //计算哈希地址
//    while (Hash[j])
//    {
//      j = (++j) % L;
//    }
//    Hash[j] = Data[i];
//  }
//}
//
//查找哈希表里的数据
//int HashSearch(int key)
//{
//  int i = key % L;        //计算哈希地址
//  while (Hash[i]&&Hash[i]!=key) //不是我要查找的值
//  {
//    i = (++i) % L;        //更换哈希地址
//  }
//  if (Hash[i]==0)     //找到开放空间的时候，查找失败
//  {
//    return -1;      //查找失败
//  }
//  else
//  {
//    return i;
//  }
//}
//
//int main()
//{
//  int key;
//  CreateHash();
//  cout << "哈希表中的值为：" << endl;
//  for (int i = 0; i < L; i++)
//  {
//    cout << Hash[i] << " ";
//  }
//  cout << endl;
//
//  cout << "请输入所要查找的值：";
//  cin >> key;
//  int IP=HashSearch(key);
//  if (IP==-1)
//  {
//    cout << "查找失败！" << endl;
//  }
//  else
//  {
//    cout << "查找成功！所对应的下标为：" << IP << endl;
//  }
//
//  return 0;
//}
//直接插入排序
//int DirInsertSortFunc(int arraa[], int length)
//{
//  int j;
//  for (int i = 2; i <=length; i++)
//  {
//    arraa[0] = arraa[i];//给监视哨赋值，a【0】用来做比较
//    j = i - 1;      //确定要比较的元素
//    while (arraa[0]<arraa[j])
//    {
//      arraa[j + 1] = arraa[j];//数据右移
//      j--;          //下标前移
//    }
//    arraa[j + 1] = arraa[0];  //在确定位置插入arraa[i]
//  }
//  return 0;
//}
//
//
//int main()
//{
//
//  cout << "插入排序:"<<endl;
//  int arry[6] = { 0,12,33,66,55,22 };
//  DirInsertSortFunc(arry, 5);
//  cout << "插入排序后的结果为：";
//  for (int i = 1; i <= 5; i++)
//  {
//    cout << arry[i] << " ";
//  }
//  cout << endl;
//  return 0;
//}
//冒泡排序
//void Func(int a[])
//{
//  int temp;
//  for (int i = 1; i < 5; i++)
//  {
//    for (int j = 0; j < 5-i; j++)
//    {
//      if (a[j]>a[j+1])
//      {
//        temp = a[j];
//        a[j] = a[j + 1];
//        a[j + 1] = temp;
//      }
//    }
//  }
//}
//
//int main()
//{
//  cout << "冒泡排序：" << endl;
//  int a[5] = { 1,55,64,99,23 };
//
//  Func(a);
//  cout << "冒泡排序的结果为：";
//  for (int i = 0; i < 5; i++)
//  {
//    cout << a[i] << " ";
//  }
//  cout << endl;
//
//  return 0;
//}
//快速排序
//int QsortFunc(int a[], int start, int end)
//{
//  int i, j;
//  i = start;      //每组首个元素给i
//  j = end;      //每组末尾元素给j
//  a[0] = a[start];  //设置基准值
//
//  while (i<j)
//  {
//    //基准值左边
//    while (i<j&&a[0]<a[j])
//    {
//      j--;  //位置左移
//    }
//    if (i<j)
//    {
//      a[i] = a[j];
//      i++;  //位置右移
//    }
//    //基准值右边
//    while (i < j&&a[i] <= a[0])
//    {
//      i++;  //位置左移
//    }
//    if (i < j)
//    {
//      a[j] = a[i];
//      j--;  //位置右移
//    }
//  }
//  a[i] = a[0];  //将基准值放入指定位置
//  if (start<i)
//  {
//    QsortFunc(a, start, j - 1);
//  }
//  if (i < end)
//  {
//    QsortFunc(a, j + 1, end);
//  }
//  return 0;
//}
//
//int main()
//{
//  cout << "快速排序：" << endl;;
//  int a[11] = { 0,66,6,666,332,12,87,45,12,45,6 };
//
//  QsortFunc(a, 1, 10);
//  cout << "快速排序的结果为：";
//  for (int i = 1; i <=10; i++)
//  {
//    cout << a[i] << " ";
//  }
//  return 0;
//}