二分查找

Given a sorted array consisting of only integers where every element appears twice except for one element which appears once. Find this single element that appears only once.
Example 1:
Input: [1,1,2,3,3,4,4,8,8]
Output: 2
Example 2:
Input: [3,3,7,7,10,11,11]
Output: 10
Note: Your solution should run in O(log n) time and O(1) space.
我们先观察一下：

值：　　1 1 2 2 4 4 5 5 9

下标：　0 1 2 3 4 5 6 7 8

此时中值为4，下标也为4。

若从头到尾都是成双成对，那偶数位的应该等于它后面的奇数位。
如果不等于，那么说明前半段出现了一个奇数。
若中值位一个奇数，若它与前面的数字相同，则说明前面都是成双成对，只有一个的数字是出现在后面。

public int singleElement(int[] a){
        int left=0;
        int right=a.length-1;
        while(left<right){
            int mid=left+(right-left)/2;
            if(mid%2==1){
                mid--;
            }
            //偶数位和奇数位相等，说明单个的元素出现在后半段
            if(a[mid]==a[mid+1]){
                left=mid+2;
            }
            else{
                right=mid;
            }
        }
        return a[left];
    }

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

Find the minimum element.

You may assume no duplicate exists in the array.

Example 1:

Input: [3,4,5,1,2]
Output: 1
Example 2:

Input: [4,5,6,7,0,1,2]
Output: 0

public int findMin(int[] a){
        int left=0;
        int right=a.length-1;
        while(left<right){
            int mid=left+(right-left)/2;

            if(a[right]<a[mid]){
                left=mid+1;
            }
            else{
                right=mid;
            }

        }
        return a[left];
    }