Algorithm Design—

Algorithm Design——查找

C++的Algorithm函数库中存在一系列的查找函数，使用起来很方便：

 1 #include<algorithm>
 2 #include<numeric>
 3 #include<functional>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     int all[14]={0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 4, 5, 6};
 9     int *a = find(all, all + 11, 8);//在all的前11个元素中查找8，如果存在，则返回8所对应的指针
10     printf_s("%d
", *a);
11 
12     int all2[4] = {4, 5, 6};
13     a = find_end(all, all + 14, all2 + 0 , all2 + 3);//找到字串all2在all中最后出现的初始位置
14     printf_s("位置：%d
", a - all);
15 
16     a = find_first_of(all, all + 14, all2 + 0 , all2 + 3);//找到字串all2在all中第一次出现的初始位置
17     printf_s("位置：%d
", a - all);
18 
19     int *sum=find_if(all,all+10,bind2nd(greater_equal<int>(), 5));//大于或等于5的第一个位置
20     printf("%d",sum-all);
21 
22     return 0;
23 }

二分查找是常用的查找方法，快速简洁：

 1 /**
 2 Binary_search主要思想：
 3     二分查找的主要思路就是设定两个指针start和end分别指向数组元素的收尾两端，
 4     然后比较数组中间结点arry[mid]和待查找元素。如果待查找元素小于中间元素，
 5     那么表明带查找元素在数组的前半段，那么将end=mid-1，如果待查找元素大于中间元素，
 6     那么表明该元素在数组的后半段，将start=mid+1;如果中间元素等于待查找元素，那么返回mid的值。 
 7 
 8 Binary_search注意事项：
 9     （1）二分查找的时间复杂度是O(log(n))，最坏情况下的时间复杂度是O(n)。 
10     （2）二分查找的一个条件是待查询的数组是有序的，我们假设这里的数组是升序的。 
11 
12 下面是Binary_search的递归和非递归版本
13 */
14 
15 #include<cstdio>
16 
17 using namespace std;
18 
19 int Binary_search(int arry[], int len, int value)
20 {
21     //如果输入序列空或者长度小于等于0，则直接返回-1
22     if(arry == NULL || len <= 0)
23         return -1;
24 
25     int start = 0;
26     int end = len - 1;
27     while(start <= end)
28     {
29         int mid = start + (end - start) / 2;
30         if(arry[mid] == value)
31             return mid;
32         else if(value < arry[mid])
33             end = mid - 1;
34         else
35             start = mid + 1;
36     }
37 
38     return  -1;
39 }
40 
41 int Binary_search_recursion(int  arry[], int value, int start, int end)
42 {
43     if(start > end)
44         return -1;
45 
46     int mid = start + (end - start) / 2;
47     if(arry[mid] == value)
48         return mid;
49     else if(value < arry[mid])
50         return Binary_search_recursion(arry, value, start, mid - 1);
51     else
52         return Binary_search_recursion(arry, value, mid + 1, end);
53 }
54 
55 int Binary_search_recursion(int arry[], int len, int value)
56 {
57     if(arry == NULL || len < 0)
58         return -1;
59 
60     return Binary_search_recursion(arry, value, 0, len - 1);
61 }
62 
63 int main()
64 {
65     int arry[] = {1, 2, 3, 4, 5, 6, 7, 8};
66     int len = sizeof(arry) / sizeof(int);
67 
68     int index = Binary_search_recursion(arry, len, 4);
69     printf_s("index:%d
", index);
70 
71     index = Binary_search_recursion(arry, len, 9);
72     printf_s("index:%d
", index);
73 }