折半查找和插值查找.txt

折半查找和插值查找

#include <stdio.h>
 int sqlList[20] = {5, 9, 13, 17, 22, 31, 47, 68, 71};

 int biSearch(int sqlList[], int num, int element) {
  int from = 0;
  int to   = num-1;
  while(from <= to) {
   int mid = (from + to) >> 1;
   if(sqlList[mid] == element)
    return mid;
   if(sqlList[mid] > element)
    to = mid - 1;
   else
    from = mid + 1;
  }
  return -1;
 }
 int insertValueSearch(int sqlList[], int num, int element) {
  int from = 0;
  int to   = num-1;
  while(from <= to) {
   int mid = (int)(from + (element - sqlList[from])
   /(sqlList[to] - sqlList[from]) * (to - from) + 0.5);
   if(sqlList[mid] == element)
    return mid;
   if(sqlList[mid] > element)
    to = mid - 1;
   else
    from = mid + 1;
  }
  return -1;
 }

 void insert(int sqlList[], int num, int element) {
  int from = 0;
  int to   = num-1;
  while(from <= to) {
   int mid = (from + to) >> 1;
   if(sqlList[mid] > element)
    to = mid-1;
   else
    from = mid+1;
  }
  for(to = num; to > from; to--)
   sqlList[to] = sqlList[to-1];
  sqlList[from] = element;
 }
 void main() {
  printf("\n\n\t\t%d\n", biSearch(sqlList, 9, 22));
  printf("\n\n\t\t%d\n", insertValueSearch(sqlList, 9, 22));
  insert(sqlList, 9, 15);
  printf("\n\n\t\t%d\n", biSearch(sqlList, 10, 15));
 }