Esta es una ligera modificación del algoritmo de búsqueda binaria. La complejidad temporal es [matemática] O (\ log_2 n) [/ matemática]
Explicación: Suponemos que la matriz es solo una matriz de enteros. Podemos convertir los índices de la matriz a un número entero e implementar un algoritmo de búsqueda binaria fácilmente.
Por ejemplo, considere la matriz: Podemos escribir esto como [matemáticas] 5,6,8,17 [/ matemáticas] con índice [matemáticas] 0,1,2,3. [/ Matemáticas]
La función transform(int *)
- ¿Cuáles son algunas buenas preguntas para la entrevista sobre Linux IPC?
- ¿Es mejor intentar oportunidades en el sitio en una empresa basada en servicios o probar una buena empresa basada en productos como 'Thought Works', donde obtendré un buen trabajo y un buen salario?
- ¿Cuál es el mejor método para verificar si un árbol binario es un árbol de búsqueda binario?
- ¿Podemos pedir más detalles sobre la entrevista con Google?
- ¿Cómo debería uno responder 'Cuéntanos sobre ti?' en una entrevista de programación?
La función reverse_transform(int)
#include #include #define SIZE 4 #define s(n) scanf("%d", &n); // Right now, it is assumed that the matrix is a square matrix. Can be modified for further use if necessary int binary_search(int matrix[][SIZE],int*,int*,int); int transform(int *); int * reverse_transform(int); int main(void) { int matrix[SIZE][SIZE]; for(int i = 0; i < SIZE; i++) { for(int j = 0; j high_int){ // Not here return -1; } else{ if(key < matrix[mid[0]][mid[1]]){ high_int = mid_int - 1; int * new_high = malloc(sizeof(int) * 2); new_high = reverse_transform(high_int); return binary_search(matrix,low,new_high,key); } else{ low_int = mid_int + 1; int * new_low = malloc(sizeof(int) * 2); new_low = reverse_transform(low_int); return binary_search(matrix,new_low,high,key); } } } int transform(int * val){ // Converts indices of a matrix to a single int // Example: Position [1,0] to 4. (in a 4x4 matrix) int ans; ans = (val[0] * SIZE) + val[1]; return ans; } int * reverse_transform(int val) { //Does the exact opposite of transform(int*) //Example Input: 10, Output: [2,2] int mult; mult = val/SIZE; int additive = val%SIZE; int * ans = malloc(sizeof(int) * 2); ans[0] = mult; ans[1] = additive; return ans; }