元素最左出现练习题

对于一个有序数组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;
    }