Question: Write a C function to find if a given integer x appears more than n/2 times in a sorted array of n integers.
METHOD 2 (Using Binary Search)
Use binary search methodology to find the first occurrence of the given number. The criteria for binary search is important here.
METHOD 1 (Using Linear Search)
Read full article from Check for Majority Element in a sorted array | GeeksforGeeks
METHOD 2 (Using Binary Search)
Use binary search methodology to find the first occurrence of the given number. The criteria for binary search is important here.
bool isMajority(int arr[], int n, int x){ /* Find the index of first occurrence of x in arr[] */ int i = _binarySearch(arr, 0, n-1, x); /* If element is not present at all, return false*/ if (i == -1) return false; /* check if the element is present more than n/2 times */ if (((i + n/2) <= (n -1)) && arr[i + n/2] == x) return true; else return false;}/* If x is present in arr[low...high] then returns the index of first occurrence of x, otherwise returns -1 */int _binarySearch(int arr[], int low, int high, int x){ if (high >= low) { int mid = (low + high)/2; /*low + (high - low)/2;*/ /* Check if arr[mid] is the first occurrence of x. arr[mid] is first occurrence if x is one of the following is true: (i) mid == 0 and arr[mid] == x (ii) arr[mid-1] < x and arr[mid] == x */ if ( (mid == 0 || x > arr[mid-1]) && (arr[mid] == x) ) return mid; else if (x > arr[mid]) return _binarySearch(arr, (mid + 1), high, x); else return _binarySearch(arr, low, (mid -1), x); } return -1;}bool isMajority(int arr[], int n, int x){ int i; /* get last index according to n (even or odd) */ int last_index = n%2? (n/2+1): (n/2); /* search for first occurrence of x in arr[]*/ for (i = 0; i < last_index; i++) { /* check if x is present and is present more than n/2 times */ if (arr[i] == x && arr[i+n/2] == x) return 1; } return 0;}Find popular item in sorted array of natural numbers.An item is popular is if its repeated n/4 times or more.This is actually a very interesting problem. Since the popular item is defined as the element is repeated more than 1 / 4 times, and since it is a sorted array, so it can only occurs on 0, n / 4, n /2 and 3n/4 index. And the rest is just do binary search and get the range.
For Ex:
Input: 123444445678
Popular item is 4.
Liner scan is O(n), but solution needs to be in O(logN) complexity and O(1) space complexity.
public static void popular(int[] n){ if(n == null || n.length == 0) return; int len = n.length; int[] check = {0, len / 4, len / 2, 3 * len / 4}; for(int i = 0; i < 4; i++){ if(i > 0 && n[check[i]] == n[check[i - 1]]) continue; int l = check[i]; int start = binarySearchStart(n, n[l]); int end = binarySearchEnd(n, n[l]); //need to be larger than the ceil in case len / 4.0 is not an integer if(end - start + 1 >= Math.ceil(len / 4.0)) System.out.println(n[l]); } } private static int binarySearchEnd(int[] n, int target){ int len = n.length; int start = 0; int end = len - 1; while(start + 1 < end){ int mid = (start + end) / 2; if(n[mid] <= target) start = mid; else end = mid; } if(n[end] == target) return end; else return start; } private static int binarySearchStart(int[] n, int target){ int len = n.length; int start = 0; int end = len - 1; while(start + 1 < end){ int mid = (start + end) / 2; if(n[mid] >= target) end = mid; else start = mid; } if(n[start] == target) return start; else return end; }