查找:根据给定的某个值,在查找表中确定一个其关键字等于给定值的记录或数据元素。若表中存在这样的一个记录,则称查找是成功的,此时查找的结果为给出整个记录的信息,或指示该记录在查找表中的位置;若表中不存在关键字等于给定值的记录,则称查找不成功,此时查找的结果可给出一个空记录或空指针。
查找表:是由同一类型的数据元素构成的集合。关键字:是数据元素(或记录)中某个数据项的值,用它可以标识一个数据元素。若此关键字可以唯一地标识一个记录,则称此关键字为主关键字;次关键字)。
折半查找:在有序表中;先确定待查记录所在的范围(区间),然后逐步缩小范围知道找到或找不到该记录为止。
/* *binarySearch *函数功能:在有序数据中利用折半查找,查找待查关键字 *输入:data[]待查找的有序数据,x待查找的关键字,low下界,high上界 *返回值:-1为查找失败,mid为查找成功 */ //非递归 int binarySearch(int data[],const int x,int low,int high){ int mid; //中间位置 if (low > high) return -1; while (low<=high){ mid = (low+high) / 2; if (x == data[mid]) return mid; else if (x > data[mid]) low = mid + 1; else if (x < data[mid]) high = mid - 1; } return -1; } //递归 int binarySearch(int data[],const int x,int low,int high){ int mid = (low + high) / 2; if (low > high) return -1; if (x == data[mid]) return mid; else if (x > data[mid]) return binarySearch(data, x, mid + 1, high); else if (x < data[mid]) return binarySearch(data,x,low,mid-1); return -1; }