zzzrf：给定一个排序的整数数组（升序）和一个要查找的整数 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;
}
}
点此查看更多题解
刷 LeetCode/LintCode 的一些心得zzzrf：我之前就是完全 0 基础、大龄转码，刷题上千然后进谷歌的…… 这里 0 基础指的是没学过编程语言，没学过数据结构和算法，一上来就直接做题那种。 第一道题 two sum，我显然不会做。**我的笨方法就是看答案，背答案，然后默出来，就这样还是错了很多次。 然而就是这样低的起点，我把 LC 前 300 道题刷了至少 3 遍，累计刷题数超过 1000 …
LeetCode题解计算机为什么是基于二进制的？可以是三进制么？二进制有什么好处？题解：为什么叫电子计算机？算盘应该没有二进制
LeetCode题解统计城市的所有灯泡这个是我刚毕业的时候，一个真实的面试题，这是一个开放题。题目描述：想办法，将一个城市的所有灯泡数量统计出来。题解：费米估算法1、如果某个城市常驻人口有1000万2、假设每5人居住在一套房里，每套房有灯泡5只，那么住宅灯泡共有1000万只3、假设公众场所每10人共享一只灯泡，那么共有100万只4、主要的这两者相加就得出了1100万只当然实际上这是估算的，具体应…
LeetCode题解黑白圆盘一个圆盘被涂上了黑白二色，两种颜色各占一个半圆。圆盘以一个未知的速度、按一个未知的方向旋转。你有一种特殊的相机可以让你即时观察到圆上的一个点的颜色。你需要多少个相机才能确定圆盘旋转的方向?题解：可以用一个相机即可
LeetCode题解圆上任取三点构成锐角三角形的概率来自字节跳动的一道几何题题解：1/4