有15个数按升序存放在一个数组中,输入一个数,要求用折半查找法找出该数是数组中第几个元素的值,如果该数不在数组中,则输出“无此数”,请编程。
时间: 2023-05-17 17:05:28 浏览: 48
以下是用 Python 实现的代码:
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid + 1
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return "无此数"
arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29]
target = int(input("请输入要查找的数:"))
result = binary_search(arr, target)
print(result)
如果输入的数在数组中,则输出该数在数组中的位置(从1开始计数),否则输出“无此数”。
相关问题
有15个数按小由到大顺序存放在一个数组中,输入一个数,要求用折半查找法找出该数在数组中的下标。
折半查找法是一种二分查找法,适用于有序数组。在数组中选择中间的数与要查找的数进行比较,如果相等,则查找成功,返回下标;如果要查找的数小于中间数,则在数组的左半部分继续查找;如果要查找的数大于中间数,则在数组的右半部分继续查找,直到找到该数为止。
有15个数按小由到大顺序存放在一个数组中,输出一个数,要求折半查找法找出该数在数组中的下标
抱歉,我可以回答您的问题。请通过二分查找法来查找该数在数组中的下标。具体实现过程如下:
将数组的中间数与需要查找的数进行比较, 如果查找的数小于中间数,则在数组前半部分继续进行查找;如果查找的数大于中间数,则在数组的后半部分继续查找。重复以上步骤,直到找到需要查找的数,或者查找范围为空。如果要查找的数不在数组中,则返回-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;
}
```
希望以上代码对您有所帮助。