Learn alongside the Code Thinking RecordReference document link:
https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html
Reference video link:https://www.bilibili.com/video/BV1fA4y1o715/vd_source=3c53b30249ab413fca24b1ab62efc8ceTraining code link (LeetCode):https://leetcode.cn/problems/binary-search/1. Binary SearchProblem:Given a sorted (ascending) array of <span>n</span> integers <span>nums</span> and a target value <span>target</span>, write a function to search for <span>target</span> in <span>nums</span>. If <span>target</span> exists, return its index; otherwise, return <span>-1</span>.There are mainly two implementations (the difference is in the definition of the search domain): 1: [left,right], defines target in a closed interval 2: [left,right), defines target in a left-closed right-open intervalSolution 1: ([left,right])
class Solution {
public:
intsearch(vector<int>&nums, inttarget) {
int left = 0;
int right = nums.size() – 1;
while(left <= right)
{
int middle = left + ((right – left) >> 1);
if(nums[middle] > target)
right = middle – 1;
elseif(nums[middle] < target)
left = middle + 1;
else
return middle;
}
return –1;
}
};
Solution 2: ([left,right))
class Solution {
public:
intsearch(vector<int>&nums, inttarget) {
int left = 0;
int right = nums.size();
while (left < right)
{
int middle = left + ((right – left) >> 1);
if(nums[middle] > target)
right = middle;
elseif(nums[middle] < target)
left = middle + 1;
else
return middle;
}
return –1;
}
};