元素最左出现练习题

对于一个有序数组arr,再给定一个整数num,请在arr中找到num这个数出现的最左边的位置。
给定一个数组arr及它的大小n,同时给定num。请返回所求位置。若该元素在数组中未出现,请返回-1。

测试样例:[1,2,3,3,4],5,3
返回:2

思路

在有序数组中查找元素, 很容易想到二分查找.
一种比较直观的想法是找到其中一个目标元素的位置后,向左开始遍历,直到到达最左边出现的位置.但是最差情况下该方法的时间复杂度是O(n).
这里我们改变二分查找的终止条件,不是找到目标节点就返回,而是逐步缩小查找范围至1.

代码:

public int findPos(int[] arr, int n, int num) {    
        int pos=-1;
        if(n==0)return pos;
        int lo=0,hi=n-1;
        int mid=0;
        
        while(lo<hi){
            mid=lo+(hi-lo)/2; // avoid overflow
            if(arr[mid]==num){
                pos=mid;
                hi=mid;
            }
            else if(arr[mid]>num){ hi=mid-1;}
            else {lo=mid+1;}
        }
        return pos;
    }
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,768评论 0 33
  • /*去重*/ function delRepeat(arr){ var newArray=new Array();...
    Hedgehog_Dove阅读 1,878评论 0 2
  • 酒坊开业后,和张家镇的人们所预期的那样,生意并没有因为换了个老板而有所起色,门前依然很是冷清。除了几个从城里...
    粟芒阅读 543评论 0 1
  • 今天,是二十四节气中的小满,这一天夏熟作物的籽粒开始灌浆饱满,但仍未成熟,只是小满,还未大满。《月令七十二候集解》...
    心灵约定阅读 1,984评论 0 2
  • 认识杰西是在大三第一学期期末考复习阶段。已经停课,每天窝在宿舍背书。某天背到生无可恋之际拿出手机刷了刷知乎,看到他...
    小烦烦烦烦阅读 313评论 0 0