二分查找更新low high为什么要mid-1
时间: 2023-05-24 11:05:55 浏览: 39
在二分查找中,每次比较中间元素与目标元素大小关系后,需要根据大小关系更新low和high的值,以缩小查找范围。具体来说,如果中间元素比目标元素大,那么目标元素只可能在左侧,因此更新high的值为mid-1,使得下一次查找范围为左侧;如果中间元素比目标元素小,那么目标元素只可能在右侧,因此更新low的值为mid+1,使得下一次查找范围为右侧。这样不断循环进行,最终就能找到目标元素或者确定其不存在。
更新low和high的过程是为了排除已经查找过的不可能存在目标元素的部分,从而缩小查找范围,加快查找速度。使用mid-1或mid+1是因为mid已经被比较过了,在下一次查找中不再需要比较,因此要排除掉。如果不更新low和high的值,那么就会出现死循环或不必要的比较,这会降低程序效率并浪费时间和空间。
相关问题
二分查找的算法,用low和high来表示当前查找区间的下界和上界,mid为中间位置
二分查找算法的基本思想是将查找区间不断缩小,直到找到目标元素或区间为空。其具体步骤如下:
1. 初始化 low 和 high 分别为查找区间的下界和上界。
2. 计算区间的中间位置 mid。
3. 如果目标元素等于 mid 处的元素,则直接返回 mid。
4. 如果目标元素小于 mid 处的元素,则在 low 到 mid-1 的区间中继续查找。
5. 如果目标元素大于 mid 处的元素,则在 mid+1 到 high 的区间中继续查找。
6. 循环执行步骤 2 到 5,直到找到目标元素或者区间为空。
下面是一个示例代码实现:
```python
def binary_search(nums, target):
low, high = 0, len(nums) - 1
while low <= high:
mid = (low + high) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
```
其中 nums 是一个已经排序的数组,target 是要查找的目标元素。如果找到目标元素,则返回其索引;否则返回 -1。
试写出二分查找的算法,用low和high来表示当前查找区间的上界和下界,mid为中间位置
好的,以下是二分查找算法的示例代码(使用C语言):
```c
int binary_search(int arr[], int n, int target) {
int low = 0, high = n-1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
```
其中,arr为待查找的有序数组,n为数组的长度,target为需要查找的目标值。在二分查找中,我们通过将查找区间不断缩小一半,来逐步逼近目标值。
在代码中,我们使用low和high来表示当前查找区间的上界和下界,初始时low为0,high为n-1。在每一轮查找中,我们通过计算mid来找到当前查找区间的中间位置。如果arr[mid]等于target,则直接返回mid;如果arr[mid]小于target,则说明目标值在mid的右侧,因此需要将查找区间缩小到mid+1到high;如果arr[mid]大于target,则说明目标值在mid的左侧,因此需要将查找区间缩小到low到mid-1。最终,如果没有找到目标值,则返回-1。
希望这个示例代码能够帮到你,如果你还有其他问题,请继续提出。