<C> 最大值以及最大值下标 二分查找（折半查找）

一.最大值以及最大值下标

#include<stdio.h>

int FindMaxIndex(int arr[],int nLen,int *p);

int main()
{
    int arr[10] = {1,5,7,3,4,6,8,9,2,0};
    int Max;
    int Index = FindMaxIndex(arr,sizeof(arr)/sizeof(arr[0]),&Max);

    return 0;
}

int FindMaxIndex(int arr[],int nLen,int *p)
{
    int i;
    int Max = 0;
    int Index;
    for(i=0;i<nLen;i++)
    {
        if(arr[i]>Max)
        {
            Max = arr[i];
            Index = i;
        }
    }
    *p = Max;
    return Index;
}

注：这个代码没什么好说的 但是需要注意的是 每个函数只能有一个返回值 但是可以加参数 通过内存空间

二.二分查找（折半查找）

1.折半查找的前提：数组是有序的

2.基本思想：

①定义一个shu 一个数组是arr[100] 这个shu在arr这个有序数组中

②定义一个int类型的变量begin=0  end=99

那么这个数组的中间元素的下标就是（0+99）/2

③作比较：

如果shu比中间元素小 说明shu在数组的前一半 end=中间元素的下标-1

如果shu比中间元素大 说明shu在数组的后一半 begin=中间元素的下标+1

④以此类推 重复这个过程 直到找到这个数为止 当然 也有可能找不到

最后应该会剩三个数 或者两个数

注：因为我们不知道循环的次数 但是begin又不可以比end大 所以我们用while循环来控制循环的次数

那begin可不可以等于end呢？ 答案是可以的！ 因为比如最后只剩下两个数的时候 没有等于号就会少比一次

PS：下面放代码 这段代码我把排序的过程也加进去了 那么最后返回的下标就是排好序之后新数组的下标

#include<stdio.h>

void BubbleSort(int arr[],int nLen);
int BinaryFind(int arr[],int nLen,int n);

int main()
{
    int arr[10] = {110,11,2,33,44,67,645,745,91,900};
    int n = 44;
    int Index;

    BubbleSort(arr,sizeof(arr)/sizeof(arr[0]));
    Index = BinaryFind(arr,sizeof(arr)/sizeof(arr[0]),44);

    return 0;
}

void BubbleSort(int arr[],int nLen)
{
    int i,j;
    for(i=0;i<nLen-1;i++)
    {
        for(j=0;j<nLen-1-i;j++)
        {
            if(arr[j] > arr[j+1])
            {
                arr[j] = arr[j] ^ arr[j+1];
                arr[j+1] = arr[j] ^ arr[j+1];
                arr[j] = arr[j] ^ arr[j+1];
            }
        }
    }
}

int BinaryFind(int arr[],int nLen,int n)
{
    int begin = 0;
    int end = nLen -1;
    int mid;

    while(begin <= end)
    {
        mid = (begin + end)/2;
        if(n > arr[mid])
        {
            begin = mid + 1;
        }
        else if(n < arr[mid])
        {
            end = mid - 1;
        }
        else
        {
            return mid;
        }
    }

    return -1;
}

3.注意：

①在BinaryFind函数中 最后return -1 是因为数组的下标是没有-1的 所以当return了-1的时候 就说明数组中 没有查找到这个你想查找的shu

②拓展：冒泡排序不需要中间变量交换两个数的方法（上面的代码中有运用到）

a = a ^ b;
b = a ^ b;
a = a ^ b;