二分查找
1 //二分查找
2 int binarySearch(int arr[], int len, int key)
3 {
4 int left = 0;
5 int right = len - 1;
6 int mid;
7
8 while (left <= right) {
9 mid = (left + right) / 2;
10 if (key < arr[mid]) {//key在左边
11 right = mid - 1;
12 } else if (arr[mid] < key) {//key在右边
13 left = mid + 1;
14 } else {
15 return mid;
16 }
17 }
18 return -1;
19 }
二分查找变形
随着二分查找的进行，如果找到key并不结束循环的话，最终的结束状态会是right < left，并且right + 1 = left。
当数组中存在key时，根据二分区间选择的不同，这里又分为两种情况，如下图（key为2时），
当数组中不存在key时，最后仅有一种情况，即把图中的黄色框框去掉。
那么，可以找到
1 最后一个小于key的元素，1，
2 第一个大于等于key的元素，2，
3 最后一个小于等于key的元素，2，
4 第一个大于key的元素，5，
另外，如果存在多个key时，稍加判断，就可以找到
5 第一个与key相等的元素
6 最后一个与key相等的元素
1 查找最后一个小于key的元素
1 //1 查找最后一个小于key的元素
2 int findLastLess(int arr[], int len, int key)
3 {
4 int left = 0;
5 int right = len - 1;
6 int mid;
7
8 while (left <= right) {
9 mid = (left + right) / 2;
10 if (key <= arr[mid]) {
11 right = mid - 1;
12 } else {
13 left = mid + 1;
14 }
15 }
16 return right;
17 }
View Code
2 查找第一个大于等于key的元素
1 //2 查找第一个大于等于key的元素
2 int findFirstGreaterEqual(int arr[], int len, int key)
3 {
4 int left = 0;
5 int right = len - 1;
6 int mid;
7
8 while (left <= right) {
9 mid = (left + right) / 2;
10 if (key <= arr[mid]) {
11 right = mid - 1;
12 }
13 else {
14 left = mid + 1;
15 }
16 }
17 return left;
18 }
View Code
3 查找最后一个小于等于key的元素
1 //3 查找最后一个小于等于key的元素
2 int findLastLessEqual(int arr[], int len, int key)
3 {
4 int left = 0;
5 int right = len - 1;
6 int mid;
7
8 while (left <= right) {
9 mid = (left + right) / 2;
10 if (key < arr[mid]) {
11 right = mid - 1;
12 } else {
13 left = mid + 1;
14 }
15 }
16 return right;
17 }
View Code
4 查找第一个大于key的元素
1 //4 查找第一个大于key的元素
2 int findFirstGreater(int arr[], int len, int key)
3 {
4 int left = 0;
5 int right = len - 1;
6 int mid;
7
8 while (left <= right) {
9 mid = (left + right) / 2;
10 if (key < arr[mid]) {
11 right = mid - 1;
12 }
13 else {
14 left = mid + 1;
15 }
16 }
17 return left;
18 }
View Code
5 查找第一个与key相等的元素
1 //5 查找第一个与key相等的元素
2 int findFirstEqual(int arr[], int len, int key)
3 {
4 int left = 0;
5 int right = len - 1;
6 int mid;
7
8 while (left <= right) {
9 mid = (left + right) / 2;
10 if (key <= arr[mid]) {
11 right = mid - 1;
12 } else {//arr[mid] < key
13 left = mid + 1;
14 }
15 }
16 //arr[right] < key <= arr[left]
17 //right是最后一个小于key的
18 //left是第一个大于等于key的
19 if (left < len && arr[left] == key) {
20 return left;
21 }
22 return -1;
23 }
View Code
6 查找最后一个与key相等的元素
1 //6 查找最后一个与key相等的元素
2 int findLastEqual(int arr[], int len, int key)
3 {
4 int left = 0;
5 int right = len - 1;
6 int mid;
7
8 while (left <= right) {
9 mid = (left + right) / 2;
10 if (key < arr[mid]) {
11 right = mid - 1;
12 } else {//arr[mid] <= key
13 left = mid + 1;
14 }
15 }
16 //arr[right] <= key < arr[left]
17 //right是最后一个小于等于key的
18 //left是第一个大于key的
19 if (right >= 0 && arr[right] == key) {
20 return right;
21 }
22 return -1;
23 }
View Code
最后补一张图，辅助理解，
怎么记呢？
看到其它博客的总结，也不错，
http://www.cnblogs.com/luoxn28/p/5767571.html
但是我觉得不够清晰好记，这里我总结为：
只要记住上面两幅图就好了，哈哈...
其实，只要记住比较符号和返回值，其它的代码都一样，
1 while (left <= right) {
2 mid = (left + right) / 2;
3 if (key ? arr[mid]) {
4 right = mid - 1;
5 } else {
6 left = mid + 1;
7 }
8 }
9 return ?;
根据要求的值的位置，先确定比较符号，再确定返回值，
比较符号：左<=，右<
返回值：左right，右left
贴一个完整的测试代码吧，
1 #include
2 using namespace std;
3
4 //二分查找
5 int binarySearch(int arr[], int len, int key)
6 {
7 int left = 0;
8 int right = len - 1;
9 int mid;
10
11 while (left <= right) {
12 mid = (left + right) / 2;
13 if (key < arr[mid]) {//key在左边
14 right = mid - 1;
15 } else if (arr[mid] < key) {//key在右边
16 left = mid + 1;
17 } else {
18 return mid;
19 }
20 }
21 return -1;
22 }
23
24 //1 查找最后一个小于key的元素
25 int findLastLess(int arr[], int len, int key)
26 {
27 int left = 0;
28 int right = len - 1;
29 int mid;
30
31 while (left <= right) {
32 mid = (left + right) / 2;
33 if (key <= arr[mid]) {
34 right = mid - 1;
35 } else {
36 left = mid + 1;
37 }
38 }
39 return right;
40 }
41
42 //2 查找第一个大于等于key的元素
43 int findFirstGreaterEqual(int arr[], int len, int key)
44 {
45 int left = 0;
46 int right = len - 1;
47 int mid;
48
49 while (left <= right) {
50 mid = (left + right) / 2;
51 if (key <= arr[mid]) {
52 right = mid - 1;
53 }
54 else {
55 left = mid + 1;
56 }
57 }
58 return left;
59 }
60
61 //3 查找最后一个小于等于key的元素
62 int findLastLessEqual(int arr[], int len, int key)
63 {
64 int left = 0;
65 int right = len - 1;
66 int mid;
67
68 while (left <= right) {
69 mid = (left + right) / 2;
70 if (key < arr[mid]) {
71 right = mid - 1;
72 } else {
73 left = mid + 1;
74 }
75 }
76 return right;
77 }
78
79 //4 查找第一个大于key的元素
80 int findFirstGreater(int arr[], int len, int key)
81 {
82 int left = 0;
83 int right = len - 1;
84 int mid;
85
86 while (left <= right) {
87 mid = (left + right) / 2;
88 if (key < arr[mid]) {
89 right = mid - 1;
90 }
91 else {
92 left = mid + 1;
93 }
94 }
95 return left;
96 }
97
98 //5 查找第一个与key相等的元素
99 int findFirstEqual(int arr[], int len, int key)
100 {
101 int left = 0;
102 int right = len - 1;
103 int mid;
104
105 while (left <= right) {
106 mid = (left + right) / 2;
107 if (key <= arr[mid]) {
108 right = mid - 1;
109 } else {//arr[mid] < key
110 left = mid + 1;
111 }
112 }
113 //arr[right] < key <= arr[left]
114 //right是最后一个小于key的
115 //left是第一个大于等于key的
116 if (left < len && arr[left] == key) {
117 return left;
118 }
119 return -1;
120 }
121
122 //6 查找最后一个与key相等的元素
123 int findLastEqual(int arr[], int len, int key)
124 {
125 int left = 0;
126 int right = len - 1;
127 int mid;
128
129 while (left <= right) {
130 mid = (left + right) / 2;
131 if (key < arr[mid]) {
132 right = mid - 1;
133 } else {//arr[mid] <= key
134 left = mid + 1;
135 }
136 }
137 //arr[right] <= key < arr[left]
138 //right是最后一个小于等于key的
139 //left是第一个大于key的
140 if (right >= 0 && arr[right] == key) {
141 return right;
142 }
143 return -1;
144 }
145
146
147 void test()
148 {
149 // int a[] = {0, 1, 2, 3, 4, 5, 6};
150 int a[] = {0, 1, 2, 2, 2, 5, 6};
151 int len = 7;
152 int key = 2;
153
154 int index;
155
156 int i;
157 for (i = 0; i < len; ++i) {
158 printf("%d ", i);
159 }
160 printf("\n");
161 for (i = 0; i < len; ++i) {
162 printf("%d ", a[i]);
163 }
164 printf("\n");
165
166 // index = binarySearch(a, 10, 2);
167 printf("%d binarySearch\n", binarySearch(a, len, key));
168 printf("%d findLastLess\n", findLastLess(a, len, key));
169 printf("%d findFirstGreaterEqual\n", findFirstGreaterEqual(a, len, key));
170 printf("%d findLastLessEqual\n", findLastLessEqual(a, len, key));
171 printf("%d findFirstGreater\n", findFirstGreater(a, len, key));
172 printf("%d findFirstEqual\n", findFirstEqual(a, len, key));
173 printf("%d findLastEqual\n", findLastEqual(a, len, key));
174 }
175
176 int main()
177 {
178 test();
179 return 0;
180 }
View Code
推荐文章
发表评论