【思想】
二分搜索主要解决的问题是确定排序后的数组x[0,n-1]中是否包含目标元素target。
二分搜索通过持续跟踪数组中包含元素target的范围(如果target存在数组中的话)来解决问题。
一开始,这个范围是整个数组,然后通过将target与数组中的中间项进行比较并抛弃一半的范围来缩小范围。该过程持续进行,
直到在数组中找到target或确定包含target的范围为空时为止。在有n个元素的表中,二分搜索大约需要执行lgn次比较操作。
提供充足的时间,竟然只有10%的专业程序员能够将这个程序编写正确。
【正解】
/*********************************
* 日期:2015-01-03
* 作者:SJF0115
* 题目: 二分查找算法
* 博客:
**********************************/
#include <iostream>
using namespace std;
int BinarySearch(int A[], int n, int target) {
if(n <= 0){
return -1;
}//if
int start = 0,end = n-1;
// 二分查找
while(start <= end){
// 中间节点
int mid = (start + end) / 2;
// 找到
if(A[mid] == target){
return mid;
}//if
else if(A[mid] > target){
end = mid - 1;
}//else
else{
start = mid + 1;
}//else
}//while
return -1;
}
int main(){
int A[] = {1,2,3,4,7,9,12};
cout<<BinarySearch(A,7,9)<<endl;
return 0;
}
【错解】
/*********************************
* 日期:2015-01-03
* 作者:SJF0115
* 题目: 二分查找算法
* 博客:
**********************************/
#include <iostream>
using namespace std;
int BinarySearch(int A[], int n, int target) {
if(n <= 0){
return -1;
}//if
int start = 0,end = n-1;
// 二分查找
while(start < end){// 错误之处
// 中间节点
int mid = (start + end) / 2;
// 找到
if(A[mid] == target){
return mid;
}//if
else if(A[mid] > target){
end = mid - 1;
}//else
else{
start = mid + 1;
}//else
}//while
return -1;
}
int main(){
int A[] = {1,2,3,4,7,9,12};
cout<<BinarySearch(A,7,3)<<endl;
return 0;
}
错误之处在代码中已经注释。主要原因是你搜索的target正好处于start = end处。例如代码中的例子。
【错解二】
/*********************************
* 日期:2015-01-03
* 作者:SJF0115
* 题目: 二分查找算法
* 博客:
**********************************/
#include <iostream>
using namespace std;
int BinarySearch(int A[], int n, int target) {
if(n <= 0){
return -1;
}//if
int start = 0,end = n-1;
// 二分查找
while(start <= end){
// 中间节点
int mid = (start + end) / 2;
// 找到
if(A[mid] == target){
return mid;
}//if
else if(A[mid] > target){
end = mid; // 可能引起错误之处
}//else
else{
start = mid; // 可能引起错误之处
}//else
}//while
return -1;
}
int main(){
int A[] = {1,2,3,4,7,9,12};
cout<<BinarySearch(A,7,12)<<endl;
return 0;
}
分享到:
相关推荐
二分查找算法二分查找算法.txt
//文件名:exp9-2.cpp #include #define MAXL 100 //定义表中最多记录个数 typedef int KeyType; typedef char InfoType[10]; typedef struct { KeyType key;
二分查找算法,二分查找算法课件,二分查找算法PPT
二分查找算法
Java二分查找递归算法
算法分析与设计-实验二 二分查找实验报告
二分查找算法是运用分治的典型例子:给定已按升序排好序的n个元素a[0:n-1],现要在这n个元素中找出一特定元素x。所以容易设计出二分搜索算法:在 a[0] [1] [n-1] 中搜索 x, 找到x时返回其在数组中的位置,否则返回-...
算法导论:二分查找算法。比较简单的算法,ACM QQ群里看到的,通俗易懂。
C 语言中效率最高的查找方式,非常实用。...函数功能: 二分查找 入口参数: 待查找有序表的首地址 int *a 待查找的数据 int num 出口参数: 查找成功返回数据在有序表中的位置0 ~ n-1,不成功返回 -1
在这个教程中,我们将深入研究二分查找算法的工作原理,并提供一个Java示例来演示如何实现它。无论您是初学者还是有经验的Java开发者,通过学习这个算法,您将获得一个强大的搜索工具,有助于在大型有序数据集中快速...
查找算法:二分查找、顺序查找的实现 参见博客:http://blog.csdn.net/xiaowei_cqu/article/details/7748260
二分查找算法是查找算法中的一种效率比较高的查找算法,对于一段数组或者字符串的查找,效率可以更高。
数据结构-查找算法 二分查找 二叉顺序数 哈希查找
java二分查找算法,用于普通的代码算法。。,。。
Java 二分查找算法的示例代码。 欢迎访问个人博客。 http://blog.csdn.net/evanwang1987