http://blog.csdn.net/sunflower_Yolanda/article/details/48497527
二、二分查找:
int BinarySearchRecursion(int arry[],int &value,int &start,int &end){ if(start>end) return -1; int mid=start+(end-start)/2; if(arry[mid]==value) return mid; else if(value<arry[mid]) { end=mid-1; return BinarySearchRecursion(arry,value,start,end); } else { start=mid+1; return BinarySearchRecursion(arry,value,start,end); }}int BinarySearchRecursion(int arry[],int &len,int &value){ //如果传入的数组为空或者数组长度<=0那么就返回-1。防御性编程 if(arry==NULL||len<=0) return -1; int start=0; int end=len-1; return BinarySearchRecursion(arry,value,start,end);}
int binarySearch(vector<int> &A, int target) { if (A.size() == 0) { return -1; } int start = 0; int end = A.size() - 1; int mid; while (start + 1 < end) { mid = start + (end - start) / 2; if (A[mid] == target) { end = mid; } else if (A[mid] < target) { start = mid; } else if (A[mid] > target) { end = mid; } } if (A[start] == target) { return start; } if (A[end] == target) { return end; } return -1; }
//给定一个排序的整数数组(升序)和一个要查找的整数target,用O(logn)的时间查找到target第一次出现的下标(从0开始),如果target不存在于数组中,返回-1。*/class Solution {public: /** * @param array source array * @param target target to search * @return the first occurrence position of target */ int binarySearch(vector<int> &A, int target) { if (A.size() == 0) { return -1; } int start = 0; int end = A.size() - 1; int mid; while (start + 1 < end) { mid = start + (end - start) / 2; if (A[mid] == target) { end = mid; } else if (A[mid] < target) { start = mid; } else if (A[mid] > target) { end = mid; } } if (A[start] == target) { return start; } if (A[end] == target) { return end; } return -1; }};
三、分块查找:
#import <Foundation/Foundation.h>struct indexBlock //定义块的结构{ int key; int start; int end;} indexBlock[4]; //定义结构体数组int main(int argc, const char * argv[]){ @autoreleasepool { int j = -1, k, x; int a[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}; for (int i = 0; i < 3; i++) { indexBlock[i].start = j + 1; //确定每个块范围的起始值 j = j + 1; indexBlock[i].end = j + 4; //确定每个块范围的结束值 j = j + 4; indexBlock[i].key = a[j]; //确定每个块范围中元素的最大值 } printf("请输入你要查找的数:\n"); scanf("%d", &x); k = blockSearch(x, a); if (k >= 0) { printf("查找成功!你要查找的数在数组中的位置是:%d\n", k+1); } else{ printf("查找失败!你要查找的数不在数组中。\n"); } } return 0;}int blockSearch(int x, int a[]){ int i = 0; int j; while (i<3 && x>indexBlock[i].key) { //确定在哪个块中 i++; } if (i >= 3) { //大于分的块数,则返回-1,找不到该数 return -1; } j = indexBlock[i].start; //j等于块范围的起始值 while (j<=indexBlock[i].end && a[j]!=x) { //在确定的块内进行查找 j++; } if (j > indexBlock[i].end) { //如果大于块范围的结束值,则说明没有要查找的数,j置为-1 j = -1; } return j;
四、二叉排序树查找:
二叉搜索树
删除
删除的节点有左子树有右子树:
B-树
五、散列查找:
参考 散列查找 哈希表 Hash
参考 字符串 hash算法
联系客服