Binary search is incredible that if I have a sorted array it just find the target element in O(long N) times, every time it search for the target element it essentially narrows down the search by half.
More details here.
C++ has built in binary search in algorithm header file, see here for more details.
simple implementation in C++
int binarySearch(std::vector<int>&nums,int target){
if(nums.empty()){
return -1;
}
int left = 0;
int right = nums.size() - 1;
while(left <= right){
int mid = left + (right - left) / 2;
if(nums[mid] == target){
return mid;
}
else if(nums[mid] < target){
left = mid + 1;
}
else{
right = mid - 1;
}
}
return -1;
}