首页 > 代码库 > [LeetCode]Search Insert Position

[LeetCode]Search Insert Position

题目:给定一个数字集合,集合中的数字按升序排列,给定一个数字target,求出数字target放置在集合中的索引值(同样按升序次序)

算法:简单比较

public class Solution {
    public int searchInsert(int[] A, int target) {
	        int i = 0;
	    	for (; i<A.length; ++i) {
	        	if (target <= A[i]) {
	        		break;
	        	}
	        }
	    	return i;
	    }
}

算法:二分查找

原理:集合数字有序,根据二分查找可不断缩小target在集合中的范围

public class Solution {
    public int searchInsert(int[] A, int target) {
	        int left = 0;
	        int right = A.length-1;
	    	int mid = (left + right) / 2;
	    	while (left <= right) {
	    		if (target == A[mid]) {
	    			break;
	    		}
	    		else if (target < A[mid]) {
	    			right = mid - 1;
	    		}
	    		else {
	    			left = mid + 1;
	    		}
	    		
	    		mid = (left + right) / 2;
	    	}
	    	
	    	if (target == A[mid]) {
	    		return mid;
	    	}
	    	else {
	    		return left;
	    	}
	    }
}