intbinarySearch(vector nums, int x) {
int left =0;
int right = nums.size();
while (left <= right) {
int mid = left + (right - left) /2;
if (nums[mid] == x)
return mid;
if (nums[mid] < x)
left = mid +1;
else right = mid -1;
}
return-1;
}
publicclassBinarySearch{publicstaticintsearch(int[] array,int target){int left = 0;int right = array.length- 1;while(left <= right){int mid =(left + right)/ 2;if(array[mid]== target){return mid;}elseif(array[mid]> target){ right = mid - 1;}else{ left = mid + 1;}}return-1;}}
Complexity
Time Complexities
Best case complexity: O(1)
Average case complexity: O(log n)
Worst case complexity: O(log n)
Space Complexity
The space complexity of the binary search is O(1).