二分法查找an的算法

二分法查找是一种在有序数组中查找特定元素的算法。其基本思想是将数组分为两部分，通过比较目标元素与数组中间元素的大小关系，确定目标元素在哪一部分，并继续在该部分进行查找，直到找到目标元素或确定目标元素不存在为止。具体算法如下：

1. 初始化数组的起始索引left为0，结束索引right为数组长度减一。
2. 循环进行以下步骤，直到left大于right：
a. 计算数组中间元素的索引mid，即mid = (left + right) // 2。
b. 比较目标元素n与数组中间元素arr[mid]的大小。
- 若n等于arr[mid]，则找到目标元素，返回mid。
- 若n小于arr[mid]，则目标元素在数组的左半部分，将right更新为mid-1。
- 若n大于arr[mid]，则目标元素在数组的右半部分，将left更新为mid+1。
3. 若循环结束仍未找到目标元素，则目标元素不存在于数组中。

这种算法的时间复杂度为O(logn)，其中n为数组的长度。