二分查找三道题

1. 二分查找
   两种写法：左闭右闭[left,right]、左闭右开[left,right)
   主要有几点不同：1. right是从num.length开始还是从num.length-1开始。2.left<=还是<right。3.right=mid还是mid+1

左闭右闭写法：

public int search(int[] nums, int target) {int left=0;int right=nums.length-1;while(left<=right){int mid=(left+right)/2;if(nums[mid]<target){left=mid+1;}else if(nums[mid]>target){right=mid-1;} else{return mid;}}return -1;}

左闭右开写法：

    public int search(int[] nums, int target) {int left=0;int right=nums.length;while(left<right){int mid=(left+right)/2;if(nums[mid]<target){left=mid+1;}else if(nums[mid]>target){right=mid;} else{return mid;}}return -1;}

3. 有重复元素的二分查找，返回重复元素的第一个位置。输入{1,2,3,3,3,3,4,5}和3，返回2

    public static void main(String[] args) {search(new int[]{1,2,3,3,3,3,4,5},3);}public static int search(int[] nums, int target) {int left = 0;int right = nums.length - 1;while (left <= right) {int mid = (left + right) / 2;if (target > nums[mid]) {left = mid + 1;} else if (target < nums[mid]) {right = mid - 1;} else {while(mid>0&&nums[mid]==nums[mid-1]){mid--;}return mid;}}return -1;}

3. leetcode540. 有序数组中的单一元素
   题目描述：给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。 请你找出并返回只出现一次的那个数。
   你设计的解决方案必须满足 o(log n) 时间复杂度和 (1)空间复杂度。

示例：
输入：nums=[1,1,2,3,3,4,4,8,8]
输出：2
输入：nums=[3,3,7,7,10,11,11]
输出：10

一般是偶数位和它后面的奇数位的数值相同。如：11223344
一旦只出现一次元素，那么就变成奇数位和后面的偶数位数值相同了。如：1123344

1. while循环终止的时候是left=right。退出的时候返回nums[left]和nums[right]都可以。

    public int singleNonDuplicate(int[] nums) {//int left=0;int right=nums.length-1;//这里不减一 会报数组越界的错while(left<right){    //左闭右开写法int mid=(left+right)/2;if(mid%2==0){if(nums[mid]==nums[mid+1]){left=mid+1;} else{right=mid;}} else{if(nums[mid]==nums[mid+1]){right=mid;} else{left=mid+1;}}}return nums[left];}