查找问题

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;
}