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