`

Leetcode - Search Insert Position

 
阅读更多
[分析] 经典二分查找,下面代码实现了迭代方式,可以验证,若直到循环结束也没有找到目标元素,则left恰好指在比target大的第一个位置, right恰好指在比target小的最后一个位置,因此返回left即可。开始没注意到这个规律,卡在循环结束该返回什么上。

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

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics