| 10 | // return the index |
| 11 | // return -1 if it does not exist |
| 12 | static int binarySearch(int[] arr, int target) { |
| 13 | int start = 0; |
| 14 | int end = arr.length - 1; |
| 15 | while(start <= end) { |
| 16 | // find the middle element |
| 17 | // int mid = (start + end) / 2; // might be possible that (start + end) exceeds the range of int in java |
| 18 | int mid = start + (end - start) / 2; |
| 19 | |
| 20 | if (target < arr[mid]) { |
| 21 | end = mid - 1; |
| 22 | } else if (target > arr[mid]) { |
| 23 | start = mid + 1; |
| 24 | } else { |
| 25 | // ans found |
| 26 | return mid; |
| 27 | } |
| 28 | } |
| 29 | return -1; |
| 30 | } |
| 31 | } |