二分查找

二分查找（折半查找）

算法效率分析：时间复杂度、空间复杂度

平均时间复杂度：O（n）；

空间复杂度：O（1）；

前提：数组元素有序

代码实现：

1，main函数内实现：

int main()

{

        int array[MAX] = { 1,2,3,5,6,7,8,9,10,11,12 };

        int length = sizeof(array) / sizeof(array[0])-1;//减1！！

        int right = array[length];

        int left = 0;//int left = array[0]不对，我们现在要的是下标不是下标对应的值

        int num;//num是要判断的值

        scanf("%d",&num);

        int MidIndex;

        while(left<=right)

        {

                MidIndex = (left + right)/2; 

                if (array[MidIndex] == num)//不是数组下标的比较MidIndex == num

                {

                        printf("该数已找到！");

                        break;

                }

                else if (array[MidIndex] < num)

                {

                         left = MidIndex + 1;

                }

                else

                {

                        right = MidIndex - 1;

                }

                if (right >= left)

                {

                        printf("该数不存在");

                        break;

                }

        }

}

2，函数封装（递归实现）

int BinarySearch0(int *arr,int length,int left,int right,int value)

{

    if (left > right)

        return -1;//不存在该数据

    int mid = ((right - left) >> 1 + left); //位运算优化

    if (arr[mid] == value)

        return mid;

    if (arr[mid] > value)//往小的那边即左边走

        return BinarySearch0(int* arr, int length, left, mid - 1, value);

    else//往大的那边即右边走

        return BinarySearch0(int* arr, int length, mid+1, left, value);

}

void BinarySearch(int *arr,int length,int value){

    int left = 0, right = len - 1;

    //封装范围

    int index = BinarySearch0(arr, length, left, right,value);

    return index;

}

int main() {

    int arr[] = { 1,2,3,4,5 };

    int len = strlen(arr);

    BinarySearch(arr, len);

    return 0;

}