给定一个排序的整数数组（升序）和一个要查找的整数 target，用 O(logn)的时间查找到 target 第一次出现的下标（从 0 开始），如果 target 不存在于数组中，返回-1 。

在线做题地址

样例 1:

输入:[1,4,4,5,7,7,8,9,9,10]，1 输出: 0          样例解释:  第一次出现在第 0 个位置。 

样例 2:

输入: [1, 2, 3, 3, 4, 5, 10]，3 输出: 2          样例解释:  第一次出现在第 2 个位置 

样例 3:

输入: [1, 2, 3, 3, 4, 5, 10]，6 输出: -1          样例解释:  没有出现过 6， 返回-1 

解题思路

题目提到，给定的数组已经排序，若从小到大遍历数组查找 target，则时间复杂度为 O(n)O(n)，n 为数组长度。需要用一个 O(logn)O(logn)的时间复杂度去完成本题，那么需要用到二分查找。

二分查找常用于查找有序数组中目标数 target 的位置，用 left 和 right 记录 target 所在的区间端点，每次将区间的中间位置值和 target 作比较，然后移动区间端点。

算法流程

• 将区间赋值为整个数组区间（ left = 0, right = n – 1 ），取中间位置 mid
• 若 a[mid] < target，则将区间缩小到原区间的右区间(left = mid + 1)
• 若 a[mid] >= target，则将区间缩小至原区间的左区间(right = mid)
• 若 left >= right 时，若 a[right] = target 则返回 right, 否则返回-1

复杂度分析

• 时间复杂度：O(logn)
• 每次查找都将区间缩小至原来长度的一半，可见查找的最多次数为 logn
• 空间复杂度：O(1)
• 查找不需要开辟新的非常数级空间，只需在原数组基础上进行查找即可

代码

public 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) {         int left = 0;         int right = nums.length - 1;         int mid;          while (left < right) {             //得到中间位置             mid = (right + left) / 2;             if (nums[mid] < target) {                 left = mid + 1;             } else {                 right = mid;             }         }          if (nums[right] == target) {             return right;         }          return -1;     } }  

点此查看更多题解