// 20190508
// Yuqiong Li
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int search(vector<int>& nums, int target) {
// base case : empty or single elements
if (nums.empty() or (nums.size() == 1 and nums.front() != target))
return -1;
else {
size_t low = 0;
// cout << "Low " << low << endl;
size_t high = nums.size() -1 ;
// cout << "High " << high << endl;
while(low <= high){
size_t mid = (low + high) / 2;
// cout << "Mid " << mid << endl;
if (target == nums[mid])
return mid;
else if (target > nums[mid])
low = mid + 1;
else{
if (mid == 0)
return -1;
else
high = mid -1;
}
}
return -1; // not found
}
}
};
int main() {
Solution s;
// vector<int> nums = {1, 2, 3, 4, 5};
vector<int> nums = {5};
// vector<int> nums = {-1,0,3,5,9,12};
int result = s.search(nums, 5);
cout << result << endl;
return 0;
}
1. Exit condition low <= high, not low < high. This will miss [5] and 5, because skip at the first condition check
2. size_t for mid will result in out of bound when mid == 0 and high = mid-1; memory error. Thus make sure high is within bound.
2. size_t for mid will result in out of bound when mid == 0 and high = mid-1; memory error. Thus make sure high is within bound.
Be the first to comment
You can use [html][/html], [css][/css], [php][/php] and more to embed the code. Urls are automatically hyperlinked. Line breaks and paragraphs are automatically generated.