二分查找法
时间: 2023-07-18 10:10:11 浏览: 45
二分查找,也称为折半查找,是一种在有序数组中查找特定元素的搜索算法。它的工作原理是将数组分成两半,然后确定要查找的元素可能存在于哪一半,然后继续在该半中查找,直到找到要查找的元素或者确定它不存在为止。
具体实现步骤如下:
1.确定数组的左右边界,分别为left和right。初始时,left为0,right为数组长度减1。
2.计算中间元素的索引mid,mid等于left和right之和除以2。
3.比较要查找的元素与中间元素的值。如果相等,返回mid。如果要查找的元素小于中间元素的值,则在左半边继续查找,更新right为mid-1;如果要查找的元素大于中间元素的值,则在右半边继续查找,更新left为mid+1。
4.重复执行第二步和第三步,直到找到要查找的元素或者确定它不存在为止。
下面是一个简单的Python实现:
```python
def binary_search(arr, left, right, target):
if left > right:
return -1
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] > target:
return binary_search(arr, left, mid-1, target)
else:
return binary_search(arr, mid+1, right, target)
```
其中,arr为要查找的有序数组,left和right为数组的左右边界,target为要查找的元素。如果找到了要查找的元素,则返回它在数组中的索引,否则返回-1。