The title
An ordered non-decrescending array that finds the position of the elements in the specified interval and prints the starting and ending subscripts. For example: 1,2,2,3,4,6 interval :2,8(greater than or equal to 2, less than or equal to 8) result 1,5 (1 is the left subscript of the interval,5 is the right subscript of the interval) require time complexity less than O(N)(can not be O(N))
Solution 1: binary search
Private int[] array = {1,2, 3,4,6}; private int min = -20; private int max = 8; public void binarySearch() { int left = binarySearch(array,min,true); int right = binarySearch(array,max,false); System.out.println(left +" "+ right); } private int binarySearch(int[] array,int target,boolean first){ int length = array.length; if (length == 0) { return -1; } if (array[0] > max) { return -1; } if (array[length-1] < min) { return -1; } int left = 0,right = length -1; while (left <= right) { int mid = left + (right -left)/2; if (array[mid] > target) { right = mid - 1; }else if (array[mid] < target) { left = mid + 1; }else { if (first) { if (mid == 0 || array[mid - 1] ! = target) { return mid; } else { right = mid - 1; } } else { if (mid == 0 || array[mid + 1] ! = target) { return mid; } else { left = mid + 1; } } } } if (first) { return left; } else { return right; }}Making the source code
This article by the blog multiple platform
OpenWriteRelease!