本关任务:已知一个规模为n的有序整数数组,再输入整数x,判断x是否在数组中,如果是,则输出相应下标,如果否,则x插入数组哪个位置能够使数组仍然有序。,给出c语言代码
时间: 2024-06-01 21:11:08 浏览: 112
输入一个数是不是在这个数组中
#include <stdio.h>
int binarySearch(int arr[], int l, int r, int x) {
if (r >= l) {
int mid = l + (r - l) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
return binarySearch(arr, mid + 1, r, x);
}
return -1;
}
int insertSorted(int arr[], int n, int x) {
int i;
for (i = n - 1; i >= 0 && arr[i] > x; i--)
arr[i + 1] = arr[i];
arr[i + 1] = x;
return (i + 1);
}
int main() {
int n, x;
printf("Enter the size of the array: ");
scanf("%d", &n);
int arr[n];
printf("Enter the elements of the array in ascending order: ");
for (int i = 0; i < n; i++)
scanf("%d", &arr[i]);
printf("Enter the element to be searched: ");
scanf("%d", &x);
int index = binarySearch(arr, 0, n - 1, x);
if (index == -1) {
printf("%d not found in the array. ", x);
int pos = insertSorted(arr, n, x);
printf("Insert %d at position %d to keep the array sorted.", x, pos);
} else
printf("%d found at position %d in the array.", x, index);
return 0;
}
阅读全文