Given a target integer T and an integer array A sorted in ascending order, find the index i such that A[i] == T or return -1 if there is no such index.
Assumptions
- There can be duplicate elements in the array, and you can return any of the indices i such that A[i] == T.
Examples
- A = {1, 2, 3, 4, 5}, T = 3, return 2
- A = {1, 2, 3, 4, 5}, T = 6, return -1
- A = {1, 2, 2, 2, 3, 4}, T = 2, return 1 or 2 or 3
Corner Cases
- What if A is null or A is of zero length? We should return -1 in this case.
1 public int binarySearch(int[] array, int target) { 2 // Write your solution here. 3 if(array == null || array.length == 0 ){ 4 return -1 ; 5 } 6 int left = 0 ; 7 int right = array.length - 1 ; 8 //since we use mid + 1 or mid - 1, here we could have left = right condition 9 while(left <= right){ 10 int mid = left + (right-left)/2 ; 11 if(array[mid] == target){ 12 return mid ; 13 } else if(array[mid]< target){ 14 left = mid + 1 ; 15 } else{ 16 right = mid - 1 ; 17 } 18 } 19 return -1; 20 }