首页 > 代码库 > 二分查找
二分查找
今天在学习《编程之美》的时候，看到一个二分查找的题目，发现原来我真的不懂二分查找。
二分查找时候注意的事项：
-
在求二分查找的中间点时没有使用
midIndex = (minIndex + maxIndex) / 2
是因为，以免 minIndex + maxIndex之后会导致溢出而出现错误。
- 注意循环的循环终止条件及边界元素的判定。
下面把牛人做的该题部分的扩展（C++）拿来展示一下，以供学习：
#include <stdlib.h>#include <string.h>#include <stdio.h>#include <iostream>using namespace std;/*//1: 给定一个有序（不降序）数组arr，求最大的i使得arr[i]等于v，不存在则返回-1int bisearch(char arr[][10], int begin, int end, char *v){ int minIndex = begin; int maxIndex = end; int midIndex; while(minIndex < maxIndex - 1) { midIndex = minIndex + (maxIndex - minIndex) / 2; if(strcmp(arr[midIndex], v) <= 0) minIndex = midIndex; else maxIndex = midIndex; } //从最大索引开始判断 if(!strcmp(arr[maxIndex], v)) return maxIndex; else if(!strcmp(arr[minIndex], v)) return minIndex; else return -1;}*//*//2: 一个有序（不降序）数组arr，求任意一个i使得arr[i]等于v,不存在则返回-1int bisearch(char (*arr)[10], int begin, int end, char *v){ int minIndex = begin; int maxIndex = end; int midIndex; while(minIndex < maxIndex) { midIndex = minIndex + (maxIndex - minIndex) / 2; if(strcmp(*(arr + midIndex), v) < 0) minIndex = midIndex + 1; else if(strcmp(*(arr + midIndex), v) > 0) maxIndex = midIndex - 1; else return midIndex; } cout << "minIndex = " << minIndex << " maxIndex = " << maxIndex << endl; if(!strcmp(*(arr + minIndex), v)) return minIndex; return -1;}*//*//3:给定一个有序（不降序）数组arr，求最小的i使得arr[i]等于v，不存在则返回-1int bisearch(char (*arr)[10], int begin, int end, char *v){ int minIndex = begin; int maxIndex = end; int midIndex; while(minIndex < maxIndex - 1) { midIndex = minIndex + (maxIndex - minIndex) / 2; if(strcmp(*(arr + midIndex), v) < 0) minIndex = midIndex; else maxIndex = midIndex; } cout << "minIndex = " << minIndex << " maxIndex = " << maxIndex << endl; //从最小数开始判断 if(!strcmp(*(arr + minIndex), v)) return minIndex; else if(!strcmp(*(arr + maxIndex), v)) return maxIndex; else return -1;}*//*//4:给定一个有序（不降序）数组arr，求最大的i使得arr[i]小于v，不存在则返回-1int bisearch(char (*arr)[10], int begin, int end, char *v){ int minIndex = begin; int maxIndex = end; int midIndex; while(minIndex < maxIndex - 1) { midIndex = minIndex + (maxIndex - minIndex) / 2; if(strcmp(*(arr + midIndex), v) < 0) minIndex = midIndex; else maxIndex = midIndex; } //从最大数开始判断 if(strcmp(*(arr + maxIndex), v) < 0) return maxIndex; else if(strcmp(*(arr + minIndex), v) < 0) return minIndex; else return -1;}*///5; 给定一个有序（不降序）数组arr，求最小的i使得arr[i]大于v，不存在则返回-1int bisearch(char (*arr)[10], int begin, int end, char *v){ int minIndex = begin; int maxIndex = end; int midIndex; while(minIndex < maxIndex - 1) { midIndex = minIndex + (maxIndex - minIndex) / 2; if(strcmp(*(arr + midIndex), v) <= 0) minIndex = midIndex; else maxIndex = midIndex; } //从小数开始判断 if(strcmp(*(arr + minIndex), v) > 0) return minIndex; else if(strcmp(*(arr + maxIndex), v) > 0) return maxIndex; else return -1;}int main(){ char a[][10] = {"abc", "bcd", "bddaaa", "ddcd", "ddd", "ddd", "ddd", "ddd", "xxx", "xxxx"}; char v[] = "dddd"; int last = sizeof(a) / (sizeof(char) * 10); int index = bisearch(a, 0, last-1, v); printf("index of v is %d\n", index); return 0;}
参考资料
[1]http://blog.csdn.net/caryaliu/article/details/8134041
二分查找
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。