1.有序数列的查找
完全写对也不容易，注意循环条件，输入的数列是从小到大的有序序列
#include <iostream>
using namespace std;
int BinarySearch(int a[],int n,int value)
{
if(n<=0) return -1;
if(n==1&& a[0]==value) return 0;
int left=0,right=n-1;
int mid;
while(left<=right)//跟边界条件配合
{
mid= left + ((right-left)>>1);//为了防止溢出
if(value<a[mid])
right=mid-1;
else if(value>a[mid])
left=mid+1;
else
return mid;
}
return -1;
}
void main()
{
int a[10]={1,2,3,4,5,6,7,8,9,10};
int x;
x=BinarySearch(a,10,9);
cout<<x<<endl;
}
2.行列递增矩阵中的元素查找
注意这里的多维数组形参的传递，比如必须要指定列号..
#include <iostream>
using namespace std;
bool YounMatrix(int a[][4],int key,int row,int col)
{
int i=0,j=col-1;
while(i<row && j>=0)
{
if(a[i][j]==key) return true;
else if(a[i][j]>key && j>0) j--;
else if(a[i][j]<key && i<row-1) i++;
}
return false;
}
void main()
{
int a[4][4]={{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};
if(YounMatrix(a,6,4,4))
cout<<"found!"<<endl;
else
cout<<"not found!"<<endl;
}
3.找到数组中出现次数超过一半的数
int FindOne(int a[], int n)
{
int candidate=a[0];
int count=0;
for(int i=0;i<n;i++)
{
if(candidate==a[i])
count++;
else
count--;
if(count==0)
{
candidate=a[i];
count=1;
}
}
return candidate;
}
