Suponga que una matriz ordenada se gira en algún pivote desconocido para usted de antemano. (es decir, 0 1 2 4 5 6 7 podría convertirse en 4 5 6 7 0 1 2).
Se le da un valor objetivo para buscar. Si se encuentra en la matriz, devuelve su índice; de lo contrario, devuelve -1. Puede asumir que no existe ningún duplicado en la matriz.
Análisis
Para utilizar la búsqueda binaria en la matriz ordenada rotada, necesitamos determinar cómo actualizar los punteros izquierdo y derecho. Hay dos casos principales, como se muestra a continuación:
Una vez que se identifican los dos casos, el problema es sencillo de resolver. Solo necesitamos verificar si el elemento de destino está en el lado ordenado y, en función de eso, mover los punteros hacia la izquierda o hacia la derecha.
Solución Java 1- Recusiva
public int search(int[] nums, int target) { return binarySearch(nums, 0, nums.length-1, target); } public int binarySearch(int[] nums, int left, int right, int target){ if(left>right) return -1; int mid = left + (right-left)/2; if(target == nums[mid]) return mid; if(nums[left] <= nums[mid]){ if(nums[left]<=target && target<nums[mid]){ return binarySearch(nums,left, mid-1, target); }else{ return binarySearch(nums, mid+1, right, target); } }else { if(nums[mid]<target&& target<=nums[right]){ return binarySearch(nums,mid+1, right, target); }else{ return binarySearch(nums, left, mid-1, target); } } } |
Solución Java 2: iterativa
public int search(int[] nums, int target) { int left = 0; int right= nums.length-1; while(left<=right){ int mid = left + (right-left)/2; if(target==nums[mid]) return mid; if(nums[left]<=nums[mid]){ if(nums[left]<=target&& target<nums[mid]){ right=mid-1; }else{ left=mid+1; } }else{ if(nums[mid]<target&& target<=nums[right]){ left=mid+1; }else{ right=mid-1; } } } return -1; } |