[二分查找程序.docVIP

二分查找 ?????? 编程珠玑第4章中提到：虽然第一篇二分有哪些信誉好的足球投注网站论文在1946年就发表了，但是第一个没有错误的二分有哪些信誉好的足球投注网站策略却直到1962年才出现，由此可见二分查找思想虽然简单，但是要写好还是很难的。 ?????? 那二分查找会出现那么多错误，主要是因为什么原因呢？ 边界问题 ?????????在二分查找的时候，边界很重要，需要理解查找的边界是什么？ ?????????边界主要可以分为[low,upper]，和[low，upper），即左闭右开、左闭右闭。这两种情况下，代码是不一样的，其不同可以参考下面的代码 /*? ????输入：A是待查找的非降序数组，n是数据的个数，key是查找的元素? ????返回：没有key，返回-1，有返回在数据中的下标? */?? int?binarySearch(?int?*A,?int?n,?int?key?)?? {?? ????int?begin?=?0;?? ????int?end???=?n;?? ????//?[0,n)?左闭右开?? ????while?(?begin??end?)?? ????{?? ????????int?mid?=?begin?+?(?end?-?begin?)?/?2;?? ????????if?(?A[mid]?==?key?)?? ????????????return?mid;?? ????????else?if?(?A[mid]??key?)?? ????????????begin?=?mid?+?1;?? ????????else?//?A[mid]??key???? ????????????end?=?mid;?? ????}?? ????return?-1;?? }?? 这个是左闭右开，所以当key A[mid]的时候，此时key在[ begin, mid)之间 int?binarySearch(?int?*A,?int?n,?int?key?)?? {?? ????int?begin?=?0;?? ????int?end???=?n;?? ????//?[0,n]?左闭右闭?? ????while?(?begin?=?end?)?? ????{?? ????????int?mid?=?begin?+?(?end?-?begin?)?/?2;?? ????????if?(?A[mid]?==?key?)?? ????????????return?mid;?? ????????else?if?(?A[mid]??key?)?? ????????????begin?=?mid?+?1;?? ????????else?//?A[mid]??key???? ????????????end?=?mid?-?1;?? ????}?? ????return?-1;?? }?? 这个是左闭右闭，所以当key A[mid]的时候，此时key在[ begin, mid-1]之间 ? 二分的优化问题 1.????查找第一个出现的位置 ?????????如果查找的数在数据中出现多次，那么返回第一个出现的位置，这个剑指offer上的面试题38差不多，此处给出实现： //?A范围是A[begin,?end]为左闭右闭?? int?getFisrtOfK(int?*A,?int?begin,?int?end,?int?key?)?? {?? ????if?(?begin??end?)?? ????????return?-1;?? ????int?mid?=?begin?+?(?end?-?begin?)?/?2;?? ????int?midData?=?A[mid];?? ?? ????if?(?midData?==??key?)?? ????{?? ????????if?(?(mid?==?0)?||?A[mid-1]?!=?key?)?? ????????????return?mid;?? ????????else??? ????????????end?=?mid?-?1;?? ????}?? ????else?if?(?midData??key?)?? ????????begin?=?mid??+?1;?? ????else?//?midData??key?? ????????end?=?mid?-?1;?? ?? ????return?getFisrtOfK(A,?begin,?end,?key);?? }?? 当我们查找到A[mid] == key的时候，此时判断前一个数是否是key，如果不是key，那么此时mid就是第一个k出现的位置，如果是key，那么此时范围缩小到A[begin, mid-1]，当A[mid]?！= key时，情况和正常情况下相似。 ??