Dada una matriz ordenada y un valor objetivo, devuelve el índice si se encuentra el objetivo. De lo contrario, devuelva el índice donde estaría si estuviera insertado en orden. Puede asumir que no hay duplicados en la matriz.
A continuación se muestran algunos ejemplos.
[1,3,5,6], 5 -> 2 [1,3,5,6], 2 -> 1 [1,3,5,6], 7 -> 4 [1,3,5,6], 0 -> 0
Solución Java
Este es un problema de búsqueda binaria. La complejidad debe ser O (log (n)).
public int searchInsert(int[] nums, int target) { if(target>nums[nums.length-1]){ return nums.length; } int l=0; int r=nums.length-1; while(l<r){ int m = l+(r-l)/2; if(target>nums[m]){ l=m+1; }else{ r=m; } } return l; } |
O de manera similar, podemos escribir la solución de la siguiente manera:
public int searchInsert(int[] nums, int target) { int i=0; int j=nums.length-1; while(i<=j){ int mid = (i+j)/2; if(target > nums[mid]){ i=mid+1; }else if(target < nums[mid]){ j=mid-1; }else{ return mid; } } return i; } |
