以下记录的都是闭区间写法
例题：34. 在排序数组中查找元素的第一个和最后一个位置
1.关系转换
寻找目标值有四种情况：≥、>、≤、<
比如目标值x， 可以转化为 ≥x、≥ x+1、≤x、≤ x+1
比如数组大小为6，目标值为5，我们将数组中最左端和最右端标记为left和right指针
2.避免溢出的写法
Mid = left+(right-left)/2
3.闭区间的含义
闭区间【L，R】中的数字都是不确定的，准确的说，是不知道具体比几大，比几小（包括边界）
我们将nums[ mid ] 和目标值 target 进行比较，nums[mid] <target ，则说明target应该在mid右边（因为闭区间，所以这个mid肯定不是，我们已经验过了），所以left指针指向mid+1，同理，如果大于等于的情况：
我们需要看这个mid的前面（左边）是否还有目标值（允许重复），同时mid也是验过了，我们将right指针指向mid-1。
总结： 我们每次移动指针，移动到的地方都是没有验过的，都是交给下一次来去验证！！！
什么时候循环结束呢？ while（left ≤ right）当left > right 的时候
如果left == right ，我们始终明确一点：【L，R】中的数字是不确定的，也就是nums[left]==nums[right] 这一个数字，我们还没验呢！！！ 怎么能结束？
最终一定存在left == right+1 吗？
是的
随着指针移动，mid的移动幅度会越来越小，后面一定是一格一格的移动，所以最后一定存在left == right ，此时不管是nums[mid] 是大于等于 target 还是 小于 target ，前者左指针加1，后者右指针减一，最终都会存在left == right + 1 .....
例1：
给你一个按照非递减顺序排列的整数数组
nums，和一个目标值target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值
target，返回[-1, -1]。你必须设计并实现时间复杂度为
O(log n)的算法解决此问题。
看到有序数字，看到时间复杂度O（log n） -> 二分查找。
其实看到有序数组就应该想到二分查找。
class Solution {
public int[] searchRange(int[] nums, int target) {
int start = Search(nums,target);
if(start == nums.length || nums[start] != target) // 优化，如果没找到start 没必要找end了
return new int[]{-1,-1};
// 这里找最后一个位置，相当于找 ≥ x+1的第一个位置的上一个位置
int end = Search(nums,target + 1) - 1;
return new int[]{start , end};
}
private int Search(int[] nums , int target){
int n = nums.length;
int left = 0 , right = n -1 ;
while(left <= right){ // 这里小于等于 ，很精髓
int mid = left+ (right-left)/2;
if(nums[mid]<target){
left = mid + 1;
}else{
right = mid -1 ;
}
}
// 这里返回right +1 也可以
return left ;
}
}最后返回的时候，返回left / right+ 1都可，因为最后的情况一定是 left == right ，然后mid =left =right，然后right = mid -1 = left -1 ；
进阶写法：通过数据的单调性去完成二分查找
例2：
给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。
请你找出并返回只出现一次的那个数。
你设计的解决方案必须满足
O(log n)时间复杂度和O(1)空间复杂度。
这题比较特殊：一个元素只出现一次，其他元素都出现两次，也就是说，以目标元素为中间值，它前面的元素，索引值为偶数的一定是其他元素，后面的元素，索引值为奇数的才是其他元素。
我们通过每次去判断索引为 2k和2k+1的值，是否相等，相等说明目标值在后面，不相等说明目标值在前面（因为目标值的存在打破了这个规律）。
我们这里除以2，乘以2
以及在定义左右指针，闭区间的话为0和（n/2）-1
都是为了避免数组越界问题
class Solution {
public int singleNonDuplicate(int[] nums) {
int n = nums.length;
int left = 0 , right = n/2 -1 ; // 注意边界，这里要减1
while(left <= right){
int mid = left+(right-left)/2;
if(nums[mid*2] == nums[mid*2+1]){
left = mid + 1;
}else{
right = mid -1;
}
}
return nums[left*2];
}
}还有一种方法，这个也是用到了答案一定在索引值为2k的上面，然后一次遍历，比较取巧.....
这是我没学二分法的想法：
class Solution {
public int singleNonDuplicate(int[] nums) {
int n = nums.length;
int k = 0 ;
if(n == 1)return nums[0];
for( ; k < n ; k = k + 2){
if( k < n-1 && nums[k]!=nums[k+1]){
return nums[k];
}
}
return nums[n-1]; // 因为答案一定存在，前面没找到则说明为数组中最后一个元素
}
}
