Given a sorted array arr[] and a number x, write a function that counts the occurrences of x in arr[]. Expected time complexity is O(Logn)
Examples:
Input: arr[] = {1, 1, 2, 2, 2, 2, 3,}, x = 2 Output: 4 // x (or 2) occurs 4 times in arr[] Input: arr[] = {1, 1, 2, 2, 2, 2, 3,}, x = 3 Output: 1 Input: arr[] = {1, 1, 2, 2, 2, 2, 3,}, x = 1 Output: 2 Input: arr[] = {1, 1, 2, 2, 2, 2, 3,}, x = 4 Output: -1 // 4 doesn't occur in arr[]Method 1 (Linear Search)Linearly search for x, count the occurrences of x and return the count.
Time Complexity: O(n)
Method 2 (Use Binary Search)1) Use Binary search to get index of the first occurrence of x in arr[]. Let the index of the first occurrence be i.2) Use Binary search to get index of the last occurrence of x in arr[]. Let the index of the last occurrence be j.3) Return (j – i + 1);
就是search for a range的变种，
search for a range的代码：
/** * 本代码由九章算法编辑提供。没有版权欢迎转发。 * - 九章算法致力于帮助更多中国人找到好的工作，教师团队均来自硅谷和国内的一线大公司在职工程师。 * - 现有的面试培训课程包括：九章算法班，系统设计班，BAT国内班 * - 更多详情请见官方网站：http://www.jiuzhang.com/ */ public class Solution { public int[] searchRange(int[] A, int target) { int start, end, mid; int[] bound = new int[2]; // search for left bound start = 0; end = A.length - 1; while (start + 1 < end) { mid = start + (end - start) / 2; if (A[mid] == target) { end = mid; //让右指针right（也就是这里的end）往左边靠拢，也就是找到第一个等于target的数。 } else if (A[mid] < target) { start = mid; } else { end = mid; } } if (A[start] == target) { bound[0] = start; } else if (A[end] == target) { bound[0] = end; } else { bound[0] = bound[1] = -1; return bound; } // search for right bound start = 0; end = A.length - 1; while (start + 1 < end) { mid = start + (end - start) / 2; if (A[mid] == target) { start = mid; //让左指针left（也就是这里的start）往右边靠拢，直到start+1<end，找到最后一个等于target的数。 } else if (A[mid] < target) { start = mid; } else { end = mid; } } if (A[end] == target) { bound[1] = end; } else if (A[start] == target) { bound[1] = start; } else { bound[0] = bound[1] = -1; return bound; } return bound; } }
转载于:https://www.cnblogs.com/hygeia/p/5152779.html
相关资源：JAVA上百实例源码以及开源项目