编辑代码

#include <iostream>
#include <stdio.h>
using namespace std;

// 折半查找，
// 输入：查找的数，有序数组，数组长度
// 输出：查找的数在数组中是否存在
bool searchSortedArray(int searchKey, int arr[], int arrLen) {
    int low = 0;            //首指针，起始值为0，即数组第一个元素
    int high = arrLen - 1;  //末尾指针，起始值为数组长度减一，即数组最后一个元素
    bool exist = false;        //记录查找的数在数组中是否存在

    while(low <= high) {
        int mid = low + ((high - low) >> 1);//计算查找的范围的中位数
        if(searchKey == arr[mid]) { //如果和中位数一致，则查找成功，退出循环
            exist = true;
            break;
        }
        else if(searchKey > arr[mid]) { //比中位数大则把范围划定在中位数后一个数到high位置
            low = mid + 1;
        }
        else {  //比中位数小则把范围划定在low位置到中位数前一个数
            high = mid - 1;
        }
    }
    //返回查找的数在数组中是否存在
    return exist;
}

// 插入排序
void insertSort(int arr[], int n) {
    if (n==0) {
        printf("数组为空\n");
        return;
    }
    // orderedNum 有序区的个数，初始为1
    for(int orderedNum = 1; orderedNum < n; orderedNum++) {
        int sortedLastIndex = orderedNum - 1;    //获取有序区最后一个元素的索引
        int sortNum = arr[orderedNum];           //获取无序区第一个元素
        for(; sortedLastIndex >= 0; sortedLastIndex--) {    //从有序区最后一个元素的索引开始向前比较
            if(arr[sortedLastIndex] > sortNum) {    //如果有序区的元素比当前排序元素大，该元素向后移
                arr[sortedLastIndex + 1] = arr[sortedLastIndex];
            } else {        //如果有序区的元素比当前排序元素小，则退出循环
                break;
            }
        }   
        arr[sortedLastIndex + 1] = sortNum;     //有序区的元素不移动后，把当前的排序元素插入到sortedLastIndex + 1的位置，即插入到有序区元素向后移之后空出来的位置
    }    
}

int main() {
    int arr[] = {85, 63, 52, 34, 25, 17, 6};
    // 1.通过插入排序将数组变为有序数组
    insertSort(arr, 7);

    // 2.查找数据元素6是否存在于数组中
    int searchKey = 6;
    if(searchSortedArray(searchKey, arr, 7)) {
        printf("%d存在于数组中\n", searchKey);
    } 
    else {
        printf("%d不存在于数组中\n", searchKey);
    }

	return 0;
}