有15个数按小由到大顺序存放在一个数组中,输出一个数,要求折半查找法找出该数在数组中的下标
时间: 2024-05-02 14:19:17 浏览: 77
抱歉,我可以回答您的问题。请通过二分查找法来查找该数在数组中的下标。具体实现过程如下:
将数组的中间数与需要查找的数进行比较, 如果查找的数小于中间数,则在数组前半部分继续进行查找;如果查找的数大于中间数,则在数组的后半部分继续查找。重复以上步骤,直到找到需要查找的数,或者查找范围为空。如果要查找的数不在数组中,则返回-1。
以下是折半查找法的实现代码:
```
int binarySearch(int arr[], int left, int right, int target){
while(left <= right){
int mid = left + (right - left)/2;
if(arr[mid] == target) //目标数等于中间数,返回中间数下标
return mid;
else if(arr[mid] < target) //目标数大于中间数,查找右半部分
left = mid + 1;
else //目标数小于中间数,查找左半部分
right = mid - 1;
}
return -1; //未找到目标数,返回-1
}
int main(){
int arr[15] = {1, 3, 5, 7, 8, 10, 12, 15, 18, 20, 25, 30, 35, 40, 45};
int target = 20; //需要查找的数
int idx = binarySearch(arr, 0, 14, target);
if(idx < 0) //未找到目标数
cout<<"要查找的数不在数组中"<<endl;
else
cout<<"要查找的数在数组中的下标是:"<<idx<<endl;
return 0;
}
```
希望以上代码对您有所帮助。
阅读全文