二分法算法

发表于 更新于 分类于

二分算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//
// Created by anska on 2022/3/6.
//
#include <vector> 
#include "iostream"
using namespace  std;
class Search{
public:
    Search(vector<int> &nums,int target){
        int left = 0;
        int right = nums.size()-1; //闭合区间[a,b]
        while(left<right){
            int middle = left +((right-left)/2);
            if(nums[middle]>target){
                right = middle-1; //target在左区间，所以[left,middle-1]
            }else if (nums[middle]<target){
                left = middle+1; //target在右区间，所以[middle+1,right];
            }else{ //找到目标值
                std::cout<<middle<<std::endl;
                return;
            }
        }
        std::cout<<-1<<std::endl;
        return;
    }
};
int main() {
    std::cout << "Hello, World!" << std::endl;
    vector<int> nums = {-1,0,3,5,9,12};
    int target = 3;
    new Search(nums,target);

    return 0;
}