Usar la búsqueda binaria con la matriz ordenada con duplicados

Se me ha encomendado la tarea de crear un método que imprima todos los índices donde se encuentra el valor x en una matriz ordenada.

Entiendo que si escaneáramos la matriz de 0 a N (longitud de la matriz), tendría un tiempo de ejecución de O (n) el peor caso. Dado que la matriz que se pasará al método se ordenará, supongo que puedo aprovechar el uso de una búsqueda binaria, ya que será O (log n). Sin embargo, esto solo funciona si la matriz tiene valores únicos. Dado que la búsqueda binaria finalizará después de la primera “búsqueda” de un valor particular. Estaba pensando en hacer una búsqueda binaria para encontrar x en la matriz ordenada, y luego verificar todos los valores antes y después de este índice, pero luego si la matriz contenía todos los valores x, no parece que sería mucho mejor.

Creo que lo que estoy preguntando es, ¿hay una mejor manera de encontrar todos los índices para un valor particular en una matriz ordenada que sea mejor que O (n)?

public void PrintIndicesForValue42(int[] sortedArrayOfInts) { // search through the sortedArrayOfInts // print all indices where we find the number 42. } 

Ej: sortedArray = {1, 13, 42, 42, 42, 77, 78} se imprimiría: “42 se encontró en los índices: 2, 3, 4”

Bueno, si realmente tiene una matriz ordenada, puede hacer una búsqueda binaria hasta que encuentre uno de los índices que está buscando, y desde allí, el rest debería ser fácil de encontrar ya que están al lado de cada uno. otro.

Una vez que haya encontrado el primero, busque todas las instancias anteriores y luego todas las instancias posteriores.

Usando ese método, debería obtener aproximadamente O (lg (n) + k) donde k es el número de ocurrencias del valor que está buscando.

EDITAR:

Y, No, nunca podrá acceder a todos los valores de k en menos del tiempo O (k) .

Segunda edición: para que pueda sentir que estoy aportando algo útil:

En lugar de buscar las primeras y últimas ocurrencias de X, puede hacer una búsqueda binaria para la primera ocurrencia y una búsqueda binaria para la última ocurrencia. que resultará en O (lg (n)) total. una vez que haya hecho eso, sabrá que todos los índices también contienen X (suponiendo que esté ordenado)

Puede hacerlo buscando si el valor es igual a x , Y si el valor a la izquierda (o a la derecha, dependiendo de si está buscando la primera aparición o la última aparición) es igual a x .

Obtendrás el resultado en O (lg n)

 public static void PrintIndicesForValue(int[] numbers, int target) { if (numbers == null) return; int low = 0, high = numbers.length - 1; // get the start index of target number int startIndex = -1; while (low <= high) { int mid = (high - low) / 2 + low; if (numbers[mid] > target) { high = mid - 1; } else if (numbers[mid] == target) { startIndex = mid; high = mid - 1; } else low = mid + 1; } // get the end index of target number int endIndex = -1; low = 0; high = numbers.length - 1; while (low <= high) { int mid = (high - low) / 2 + low; if (numbers[mid] > target) { high = mid - 1; } else if (numbers[mid] == target) { endIndex = mid; low = mid + 1; } else low = mid + 1; } if (startIndex != -1 && endIndex != -1){ for(int i=0; i+startIndex<=endIndex;i++){ if(i>0) System.out.print(','); System.out.print(i+startIndex); } } } 
 public void PrintIndicesForValue42(int[] sortedArrayOfInts) { int index_occurrence_of_42 = left = right = binarySearch(sortedArrayOfInts, 42); while (left - 1 >= 0) { if (sortedArrayOfInts[left-1] == 42) left--; } while (right + 1 < sortedArrayOfInts.length) { if (sortedArrayOfInts[right+1] == 42) right++; } System.out.println("Indices are from: " + left + " to " + right); } 

Esto se ejecutaría en O (log (n) + #currencias). Lea y entienda el código. Es bastante simple.

Un Hashmap podría funcionar, si no está obligado a utilizar una búsqueda binaria.

Cree un HashMap donde la Key es el valor en sí mismo, y luego el valor es una matriz de índices donde ese valor está en la matriz. Recorra su matriz, actualizando cada matriz en el HashMap para cada valor.

El tiempo de búsqueda de los índices para cada valor será ~ O (1), y la creación del mapa en sí será ~ O (n).

 Find_Key(int arr[], int size, int key){ int begin = 0; int end = size - 1; int mid = end / 2; int res = INT_MIN; while (begin != mid) { if (arr[mid] < key) begin = mid; else { end = mid; if(arr[mid] == key) res = mid; } mid = (end + begin )/2; } return res; } 

Suponiendo que la matriz de ints está en orden ascendente ordenado; Devuelve el índice del primer índice de ocurrencia de clave o INT_MIN. Se ejecuta en O (lg n).

A continuación se muestra el código java que devuelve el rango para el cual la clave de búsqueda se extiende en la matriz ordenada:

 public static int doBinarySearchRec(int[] array, int start, int end, int n) { if (start > end) { return -1; } int mid = start + (end - start) / 2; if (n == array[mid]) { return mid; } else if (n < array[mid]) { return doBinarySearchRec(array, start, mid - 1, n); } else { return doBinarySearchRec(array, mid + 1, end, n); } } /** * Given a sorted array with duplicates and a number, find the range in the * form of (startIndex, endIndex) of that number. For example, * * find_range({0 2 3 3 3 10 10}, 3) should return (2,4). find_range({0 2 3 3 * 3 10 10}, 6) should return (-1,-1). The array and the number of * duplicates can be large. * */ public static int[] binarySearchArrayWithDup(int[] array, int n) { if (null == array) { return null; } int firstMatch = doBinarySearchRec(array, 0, array.length - 1, n); int[] resultArray = { -1, -1 }; if (firstMatch == -1) { return resultArray; } int leftMost = firstMatch; int rightMost = firstMatch; for (int result = doBinarySearchRec(array, 0, leftMost - 1, n); result != -1;) { leftMost = result; result = doBinarySearchRec(array, 0, leftMost - 1, n); } for (int result = doBinarySearchRec(array, rightMost + 1, array.length - 1, n); result != -1;) { rightMost = result; result = doBinarySearchRec(array, rightMost + 1, array.length - 1, n); } resultArray[0] = leftMost; resultArray[1] = rightMost; return resultArray; } 

Está utilizando la búsqueda binaria modificada. Será O (LogN). La complejidad del espacio será O (1). Estamos llamando a BinarySearchModified dos veces. Uno para encontrar el índice de inicio del elemento y otro para encontrar el índice final del elemento.

 private static int BinarySearchModified(int[] input, double toSearch) { int start = 0; int end = input.Length - 1; while (start <= end) { int mid = start + (end - start)/2; if (toSearch < input[mid]) end = mid - 1; else start = mid + 1; } return start; } public static Result GetRange(int[] input, int toSearch) { if (input == null) return new Result(-1, -1); int low = BinarySearchModified(input, toSearch - 0.5); if ((low >= input.Length) || (input[low] != toSearch)) return new Result(-1, -1); int high = BinarySearchModified(input, toSearch + 0.5); return new Result(low, high - 1); } public struct Result { public int LowIndex; public int HighIndex; public Result(int low, int high) { LowIndex = low; HighIndex = high; } } 

Se me ocurrió la solución utilizando la búsqueda binaria, lo único es hacer la búsqueda binaria en ambos lados si se encuentra la coincidencia.

 public static void main(String[] args) { int a[] ={1,2,2,5,5,6,8,9,10}; System.out.println(2+" IS AVAILABLE AT = "+findDuplicateOfN(a, 0, a.length-1, 2)); System.out.println(5+" IS AVAILABLE AT = "+findDuplicateOfN(a, 0, a.length-1, 5)); int a1[] ={2,2,2,2,2,2,2,2,2}; System.out.println(2+" IS AVAILABLE AT = "+findDuplicateOfN(a1, 0, a1.length-1, 2)); int a2[] ={1,2,3,4,5,6,7,8,9}; System.out.println(10+" IS AVAILABLE AT = "+findDuplicateOfN(a2, 0, a2.length-1, 10)); } public static String findDuplicateOfN(int[] a, int l, int h, int x){ if(l>h){ return ""; } int m = (hl)/2+l; if(a[m] == x){ String matchedIndexs = ""+m; matchedIndexs = matchedIndexs+findDuplicateOfN(a, l, m-1, x); matchedIndexs = matchedIndexs+findDuplicateOfN(a, m+1, h, x); return matchedIndexs; }else if(a[m]>x){ return findDuplicateOfN(a, l, m-1, x); }else{ return findDuplicateOfN(a, m+1, h, x); } } 2 IS AVAILABLE AT = 12 5 IS AVAILABLE AT = 43 2 IS AVAILABLE AT = 410236578 10 IS AVAILABLE AT = 

Creo que esto todavía está proporcionando los resultados en O (logn) complejidad.

 public void printCopies(int[] array) { HashMap memberMap = new HashMap(); for(int i = 0; i < array.size; i++) if(!memberMap.contains(array[i])) memberMap.put(array[i], 1); else { int temp = memberMap.get(array[i]); //get the number of occurances memberMap.put(array[i], ++temp); //increment his occurance } //check keys which occured more than once //dump them in a ArrayList //return this ArrayList } 

Alternativamente, en lugar de contar el número de ocurrencias, puede poner sus índices en un arrailista y poner eso en el mapa en lugar del recuento.

  HashMap> //the integer is the value, the arraylist a list of their indices public void printCopies(int[] array) { HashMap> memberMap = new HashMap>(); for(int i = 0; i < array.size; i++) if(!memberMap.contains(array[i])) { ArrayList temp = new ArrayList(); temp.add(i); memberMap.put(array[i], temp); } else { ArrayList temp = memberMap.get(array[i]); //get the lsit of indices temp.add(i); memberMap.put(array[i], temp); //update the index list } //check keys which return lists with length > 1 //handle the result any way you want } 

je, supongo que esto tendrá que ser publicado.

  int predefinedDuplicate = //value here; int index = Arrays.binarySearch(array, predefinedDuplicate); int leftIndex, rightIndex; //search left for(leftIndex = index; array[leftIndex] == array[index]; leftIndex--); //let it run thru it //leftIndex is now the first different element to the left of this duplicate number string for(rightIndex = index; array[rightIndex] == array[index]; rightIndex++); //let it run thru it //right index contains the first different element to the right of the string //you can arraycopy this [leftIndex+1, rightIndex-1] string or just print it for(int i = leftIndex+1; i 

Otro resultado para la búsqueda binaria log (n) para el destino más a la izquierda y el más a la derecha. Esto está en C ++, pero creo que es bastante legible.

La idea es que siempre terminamos cuando left = right + 1 . Por lo tanto, para encontrar el objective más a la izquierda, si podemos movernos hacia la derecha hacia el número más a la derecha que es menor que el objective, la izquierda estará en el objective que está más a la izquierda.

Para el objective más a la izquierda:

 int binary_search(vector& nums, int target){ int n = nums.size(); int left = 0, right = n - 1; // carry right to the greatest number which is less than target. while(left <= right){ int mid = (left + right) / 2; if(nums[mid] < target) left = mid + 1; else right = mid - 1; } // when we are here, right is at the index of greatest number // which is less than target and since left is at the next, // it is at the first target's index return left; } 

Para el objective más a la derecha, la idea es muy similar:

 int binary_search(vector& nums, int target){ while(left <= right){ int mid = (left + right) / 2; // carry left to the smallest number which is greater than target. if(nums[mid] <= target) left = mid + 1; else right = mid - 1; } // when we are here, left is at the index of smallest number // which is greater than target and since right is at the next, // it is at the first target's index return right; }