二分查找
题目解析：在一个有序数组中找一个 target，找到返回其下标，找不到返回 -1。 算法原理：
- 暴力解法：遍历整个数组进行查找，时间复杂度 O(N)。
- 朴素二分算法：数组具有'二段性'，可以根据中间值将数组分为两部分并舍弃一部分，使用二分算法可将效率提升至 O(log N)。
class Solution {
public int search(int[] nums, int target) {
// 使用 left 和 right 两个变量在左右两边
// 使用 mid 来表示其中间的下标，因为其有序
// 这样我们每次比较一次其就会干掉一半的数，这个效率是很高的
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // 防溢出
if (target > nums[mid]) {
// 在 [mid+1 , right]
left = mid + 1;
} else if (target < nums[mid]) {
// 在 [left, mid - 1]
right = mid - 1;
} else {
return mid;
}
}
return -1;
}
}
时间复杂度：O(log N) 空间复杂度：O(1)
在排序数组中查找元素的第一个和最后一个位置
：给定一个 target，在非递减数组中找其开始和结束下标，并返回。如果找不到就返回 [-1, -1]。 ：
