设为首页 - 加入收藏 焦点技术网
热搜:java
当前位置:首页 >

Search Insert Position -- LeetCode

2014-03-02 07:40:00.0 LeetCode leetcode java 二分查找 面试 search  
导读:原题链接: http://oj.leetcode.com/problems/search-insert-position/ 这道题比较简单,就是二分查找。思路就是每次取中间,如果等于目标即返回,否则根据大小关系切去一半。因此算法复杂度是O(logn),空间复杂度O(1)。代码如下: public int searchInsert(int[] A, int target) { if(A == ...。。。
原题链接: http://oj.leetcode.com/problems/search-insert-position/ 

这道题比较简单,就是二分查找。思路就是每次取中间,如果等于目标即返回,否则根据大小关系切去一半。因此算法复杂度是O(logn),空间复杂度O(1)。代码如下: 

public int searchInsert(int[] A, int target) {    if(A == null || A.length == 0)    {        return 0;    }    int l = 0;    int r = A.length-1;    while(l<=r)    {        int mid = (l+r)/2;        if(A[mid]==target)            return mid;        if(A[mid]注意以上实现方式有一个好处,就是当循环结束时,如果没有找到目标元素,那么l一定停在恰好比目标大的index上,r一定停在恰好比目标小的index上,所以个人比较推荐这种实现方式。
二分查找是一个非常经典的方法,不过一般在面试中很少直接考二分查找,会考一些变体,例如Search in Rotated Sorted ArraySearch for a RangeSearch a 2D Matrix,思路其实是类似的,稍微变体一下即可,有兴趣可以练习一下哈。

(编辑: linhuanmars)

网友评论