（1）二分查找

二分查找

「二分查找 binary search」是一种基于分治策略的高效搜索算法。它利用数据的有序性，每轮缩小一半搜索范围，直至找到目标元素或搜索区间为空为止。

给定一个长度为 n 的数组 nums ，元素按从小到大的顺序排列且不重复。请查找并返回元素 target 在该数组中的索引。若数组不包含该元素，则返回 −1

int main(){
    int arr[10] = {1,2,3,4,5,6,7,8,9,10};
    int targect = 10;
    int l = 0;
    int r = 9;
    while(l<r){
        int mid = (l+r)/2;
        if(arr[mid] == targect){
            l = mid;
        }else if(arr[mid] > targect){
            r = mid - 1;
        }else{
            l = mid + 1;
        }
    }
    cout<<l;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

思路

1. 初始化指针l = 0,r=arr.size()-1，分别指向数组的首元素和尾元素，代表搜索区间[0，arr.size()-1]
2. 接下来循环执行以下步骤
3. 计算中间索引mid = (l+r)/2
4. 判断arr[mid] 和 target的大小关系，分三种情况
5. 当arr[mid] > target时，说明target在区间[l,mid-1],执行r=mid-1
6. 当arr[mid] < target时，说明target在区间[mid+1,r],执行l=mid+1
7. 当arr[mid] = target时，说明找到了目标值，直接返回mid

优点与局限性

• 二分查找的时间效率高，时间复杂度为logn

• 二分查找无需额外的空间

• 二分查找仅适用于有序数据，若数据无需，则需要先对数据进行排序才可以使用二分查找