在计算机科学中，折半搜索，也称二分查找算法、二分搜索，是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
1
/**//*
2
名称：二分查找
3 时间复杂度：O(lg (n))
4
*/
5
#include <iostream>
6#include <time.h>
7#include <stdlib.h>
8using namespace std;
9void mergeSort(int*, int);
10void __mergeSort(int*, int, int);
11void merge(int*, int, int, int);
12int binarySearch(int*, int, int);
13int main(void)
14
{
15 int n;
16 int *array;
17
srand(time(NULL)); /**//*void srand(unsigned seed)；*/
18 while (true)
19 {
20 cin >> n;
21 array = new int[n];
22 /**//*随机生成数组*/
23 for (int i = 0; i < n; ++i)
24 {
25 array[i] = rand() % 100; /**//*int rand(void)；*/
26
}
27
28 /**//*排序前*/
29 for (int i = 0; i < n; ++i)
30 {
31 cout << array[i] << ' ';
32 }
33 cout << endl;
34
35 /**//*归并排序*/
36 mergeSort(array, n);
37
38 /**//*排序后*/
39 for (int i = 0; i < n; ++i)
40 {
41 cout << array[i] << ' ';
42 }
43 cout << endl;
44
45 /**//*二分查找*/
46 int value;
47 cin >> value;
48 cout << binarySearch(array, n ,value) << endl;
49 delete array;
50 }
51 return 0;
52}
53void mergeSort(int* array, int length)
54{
55 __mergeSort(array, 0, length - 1);
56}
57void __mergeSort(int* array, int first, int last)
58{
59 /**//*只有有两个元素*/
60 if (first < last)
61 {
62 int middle = first + (last - first) / 2;
63 __mergeSort(array, first, middle);
64 __mergeSort(array, middle + 1, last);
65 merge(array, first, middle, last);
66 }
67}
68void merge(int* array, int first, int middle, int last)
69{
70 int* temp = new int[last - first + 1];
71 int i = first;
72 int j = middle + 1;
73 int k = 0;
74 while (i <= middle && j <= last)
75 {
76 /**//*取较小者*/
77 if (array[i] <= array[j])
78 {
79 temp[k] = array[i];
80 ++i;
81 }
82 else
83 {
84 temp[k] = array[j];
85 ++j;
86 }
87 ++k;
88 }
89 /**//*前半部分没有复制完*/
90 if (i <= middle)
91 {
92 while (i <= middle)
93 {
94 temp[k] = array[i];
95 ++i;
96 ++k;
97 }
98 }
99 /**//*后半部分没有复制完*/
100 if (j <= last)
101 {
102 while (j <= last)
103 {
104 temp[k] = array[j];
105 ++j;
106 ++k;
107 }
108 }
109 /**//*复制回原数组*/
110 for (int p = first, q = 0; p <= last; ++p, ++ q)
111 {
112 array[p] = temp[q];
113 }
114 /**//*释放内存*/
115 delete temp;
116}
117int binarySearch(int* array, int length, int value)
118{
119 int left = 0;
120 int right = length - 1;
121 while (left <= right)
122 {
123 int middle = left + ((right - left) >> 1);
124 if (array[middle] < value)
125 {
126 left = middle + 1;
127 }
128 else if (array[middle] > value)
129 {
130 right = middle - 1;
131 }
132 else
133 {
134 return middle;
135 }
136 }
137 return -1;
138}
139
posted on 2012-10-21 23:48
zhuxin 阅读(75)
评论(0) 编辑 收藏 引用 所属分类:
数据结构和算法