| 9 | |
| 10 | // return the index of smallest no >= target |
| 11 | static int ceiling(int[] arr, int target) { |
| 12 | |
| 13 | // but what if the target is greater than the greatest number in the array |
| 14 | if (target > arr[arr.length - 1]) { |
| 15 | return -1; |
| 16 | } |
| 17 | int start = 0; |
| 18 | int end = arr.length - 1; |
| 19 | |
| 20 | while(start <= end) { |
| 21 | // find the middle element |
| 22 | // int mid = (start + end) / 2; // might be possible that (start + end) exceeds the range of int in java |
| 23 | int mid = start + (end - start) / 2; |
| 24 | |
| 25 | if (target < arr[mid]) { |
| 26 | end = mid - 1; |
| 27 | } else if (target > arr[mid]) { |
| 28 | start = mid + 1; |
| 29 | } else { |
| 30 | // ans found |
| 31 | return mid; |
| 32 | } |
| 33 | } |
| 34 | return start; |
| 35 | } |
| 36 | } |