1. 二分查找

1.1 经典二分-查找有序数组中存在的元素

public static boolean exist(int[] sortedArr, int num) {
    if (sortedArr == null || sortedArr.length == 0) {
        return false;
    }
    int L = 0;
    int R = sortedArr.length - 1;
    int mid = 0;
    // L..R
    while (L < R) { // L..R 至少两个数的时候
        mid = L + ((R - L) >> 1);
        if (sortedArr[mid] == num) {
            return true;
        } else if (sortedArr[mid] > num) {
            R = mid - 1;
        } else {
            L = mid + 1;
        }
    }
    return sortedArr[L] == num;
}

1.2 查找有序数组中满足>=vlaue的最左位置

public static int nearestIndex(int[] arr, int value) {
    int L = 0;
    int R = arr.length - 1;
    int index = -1; // 记录最左的对号
    while (L <= R) { // 至少一个数的时候
        int mid = L + ((R - L) >> 1);
        if (arr[mid] >= value) {
            index = mid;  // 记录当前满足条件的位置，
            R = mid - 1;  // 向左找继续二分，看是否还有满足条件的位置
        } else {
            L = mid + 1;
        }
    }
    return index;
}

1.3 查找有序数组中满足<=value的最右位置

public static int nearestIndex(int[] arr, int value) {
    int L = 0;
    int R = arr.length - 1;
    int index = -1; // 记录最右的对号
    while (L <= R) {
        int mid = L + ((R - L) >> 1);
        if (arr[mid] <= value) {
            index = mid; // 记录当前满足条件的位置
            L = mid + 1; // 向右找看是否还有满足条件的位置
        } else {
            R = mid - 1;
        }
    }
    return index;
}

2. 异或运算（*无进位相加）

• 相同得0，不同得1（无进位相加，二进制相加不进位。）
• 相同
• 异或操作性质：
  • (1) 零与任何数异或都为数本身 0^N = N
  • (2) 任何数与本身异或都为0 N^N = 0
  • (3) 异或运算满足交换律和结合律 a^b = b^a (a^b)^c = a^(b^c) 异或顺序不影响最终0果。

    3. 异或相关的算法题目

    3.1 题目一 值交换

题目描述： 如何不用额外变量交换两个变量的值？

a = a^b   // a=a^b; b=b
b = a^b   // b=a^b^b=a; a=a^b
a = a^b   // a=a^b^a=b;

算法实现：

/**
 * 使用位运算实现两个变量值的交换。
 *      使用的前提：两个变量所指的内存区域不是同一块内存空间。
 *      如果是同一个位置就会导致结果为0。
 *
 */
public class example1 {
    public static void main(String[] args) {
        int a = 16;
        int b = 6;
        //使用异或的性质来交换两个数的值
        a = a^b;
        b = a^b;
        a = a^b;
        System.out.println(a);
        System.out.println(b);
        //测试对内存中同一个位置上的数字进行异或操作交换
        int arr[] = {1,2};
        int i=0,j=0;
        arr[i] =  arr[i] ^ arr[j];
        arr[j] =  arr[i] ^ arr[j];
        arr[i] =  arr[i] ^ arr[j];
        System.out.println(arr[i]);
        System.out.println(arr[j]);
    }
}

3.2 题目二 奇数统计

题目描述： 一个数组中一种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这个出现了奇数次的数字。

• 传统做法：
  • 对于这种题目传统的做法就是使用哈希表统计数组中每个数组出现的个数。
• 经典做法：
  • 使用位运算的性质，只需要一个变量就可以实现，极大的优化了算法的空间复杂度。

    分析： 由于数组中只有一种数字出现了奇数次，其他的都是偶数次，根据位运算的性质，一个数与其本身进行异或运算，则结果为0，所以数组中出现偶数个的数进行异或结果都为0，最后与奇数个的那个数相异或得到的就是出现次数为奇数个的数本身。

算法实现：

public class example2 {
    public static void main(String[] args) {
        int arr[] = {1,2,3,4,1,2,3,1,2,3,1,2,3};  // 异或顺序不影响结果。
        //申请一个变量
        int xor = 0;
        for (int each : arr) {
            xor = xor ^ each;
        }
        System.out.println("数组中的出现了奇数次数为："+xor);
    }
}
// 数组中的出现了奇数次数为：4

3.3 题目三 双奇数统计

• 前置知识点：整数a的相反数 = a取反加1 -a = ~a + 1
  • 案例如下：
  • 通过 a&(-a) 能够得到该整数对应二进制位最右侧位上的1，同时其他位都为0。

                  a = 0110 1000          
                ~a = 1001 0111
            ~a+1 = 1001 1000 
        a & (-a)  = 0000 1000

题目描述： 一个数组中有两种数出现了奇数次，其他数都出现了偶数次，怎么找到这两种数？

分析： 通过题目2，可以想到将数组中所有的元素进行异或操作，偶数的都为0，但是该数组中有两种数出现次数是奇数次，假设为，a，b。最后异或得到的结果 eor = a^b。如何将 a和b剥离开来？ 通过位运算找到一个 eor 二进制位为1的一个位置，通过前置知识我们可以通过eor & (-eor)来获取eor最右侧（假设为第n位）为1数 rightOne，则可以得到，第n位上 a 和 b 一定是不同的，可以通过 rightOne 和数组中的值逐个进行与操作，通过判断结果是否为0，可以将第n位置为1的所有数分为一个阵营，不为1的分为另外一个阵营，同时也将a和b分开了。 假如 a 的第n位为1，如题二，将0与第n位置为1的这一个阵营中的所有数进行异或操作，最后可以得到a的值，因为阵营1中除了a之外，就是出现偶数次的数了，通过异或运算可以清除出现偶数次的数。 a的值得到之后，再与eor进行异或操作，就可以得到b的值了。

代码实现：

public static void main(String[] args) {
    int arr[] = {1,2,3,3,4,4,5,5,5,5};
    int eor = 0;
    for (int each: arr){
        eor = eor ^ each;
    }
    // 最后得到的结果 eor = a^b; //假设a和b是两种出现了奇数次的数
    // 找到eor最右侧位置上的1,该位置上a和b一定是不同的，通过该位置的状态将a和b区分开来。
    /**
     * eor = a^b
     * eor 最右侧为1的数，提取出来 rightOne
     * eg:
     *      eor: 0011 1100 0001 1000
     * rightOne: 0000 0000 0001 0000
     *
     */
    int rightOne = eor & (-eor);
    //通过rightOne将a 和 b两个数分开
    int onlyOne = 0;
    for (int each : arr) {
        if ((each & rightOne) != 0){  //对应位置为1的数, 通过异或可以得到该位置上为1的数。
            onlyOne = onlyOne ^ each;
        }
    }
    int oneNum = onlyOne;
    int anotherNum = onlyOne ^ eor;
    System.out.println("oneNum:"+oneNum+"\nanother:"+anotherNum);
}
//oneNum:1
//another:2