数据结构 - 二分查找

注意事项

• 二分查找针对有序数组
• 时间复杂度：O(logn)

代码实现

• 注意：初始化：left=0, right=nums.size()-1，搜索的范围是[left, right]，前闭后闭区间；
• 循环继续执行的条件：left <= right

#include <iostream>
#include <vector>
using namespace std;

/**
 * 二分查找
 * @param nums
 * @param target
 * @return
 */
int binary_search(vector<int> nums, int target){
    if(nums.size() < 1)
        return -1;

    // 在[left, right]中查找
    int left=0, right=nums.size()-1;

    while(left <= right){
        int mid=(left+right)/2;
        if(nums[mid] == target)
            return mid;

        if(target > nums[mid])
            left = mid+1;
        else
            right = mid-1;
    }

    return -1;
}

int main(){

    vector<int> nums={1,3,5,7,9,11};
    cout<<binary_search(nums, 7)<<endl;


    return 0;
}