题目
描述
给定一个排序的整数数组（升序）和一个要查找的整数target，用O(logn)的时间查找到target第一次出现的下标（从0开始），如果target不存在于数组中，返回-1。
样例
在数组[1, 2, 3, 3, 4, 5, 10] 中二分查找3，返回2。
解答
思路
基础题。解释见注释。
代码
class Solution {
/**
* @param nums: The integer array.
* @param target: Target to find.
* @return: The first position of target. Position starts from 0.
*/
public int binarySearch(int[] nums, int target) {
//write your code here
//从两头往中间遍历
int low = 0, high = nums.length;
//直到两个游标相遇
while(low <= high){
//比较位于中间的数和目标数
int middle = (high + low) / 2;
//若位于中间的数等于目标数
if(nums[middle] == target){
//若中间游标为0，返回0
if(middle == 0) return (0);
//注意，题中要求出现的第一次，因此要往前回溯
else{
while(nums[middle - 1] == target) middle--;
//返回第一次出现的位置
return middle;
}
}
//若中位数大于目标数，右游标设为中间位置右边
if(nums[middle] > target) high = middle - 1;
//若中文数小于目标书，左游标设为中间位置左边
else low = middle + 1;
}
//没有找到，返回-1
return (-1);
}
}
