二分搜索（Binary Search）

• 如何确定一个元素在数组中的位置？（假设数组里面全都是整数）

• 如果是无序数组，从第0个位置开始遍历搜索，平均时间复杂度：O(n)
  

• 如果是有序数组，可以使用二分搜索，最坏时间复杂度为O(logn)
  

（一）、二分搜索 — 思路

• 假设在[begin，end）范围内搜索某个元素 v，mid == （begin + end）/ 2
  ①、如果v < m，去[begin ， mid）范围内二分搜索
  ②、如果v > m，去[mid + 1， end）范围内二分搜索
  ③、如果v == m ，直接返回 mid
• end指的是数组的长度。
  

（二）、二分搜索 — 实例

（三）、二分搜索 — 实现

import org.junit.Test;
import java.util.Arrays;

/**
* 查找v在有序数组array中的位置
*/
public class BinarySearch {
    public int indexOf(int[] array, int v){
        if (array == null || array.length == 0) return -1;
        int begin = 0;
        int end = array.length;
        while (begin < end){
            int mid = (begin + end) >> 1;
            if (v < array[mid]){
                end = mid;
            }else if (v > array[mid]){
                begin = mid+1;
            }else {
                return mid;
            }
        }
        return -1;
    }
    @Test
    public void test(){
        int[] array = {2,4,8,8,9,13,10};
        System.out.println(Arrays.toString(array));
        System.out.println(indexOf(array,8));
    }
}
运行结果：
[2, 4, 6, 8, 9, 13, 10]
3

• 思考？？？
  如果存在多个重复的值，返回的是哪一个？
• 例如：[2，4， 8， 8， 9， 13， 10]
  我们通过运行上述的代码，可以看到，它的返回值是3，而不是2，因此我们可以得出结论如果存在多个重复的值，返回的值不确定。

（四）、二分搜索优化

• 在元素 v 的插入过程中，可以先用二分搜索出合适的插入位置，然后再将元素v插入。
  
• 要求二分搜索返回的插入位置：第1个大于 v 的元素位置
  ①、如果 v 是 5，返回 2
  ②、如果 v 是 1，返回 0
  ③、如果 v 是 15，返回 7
  ④、如果 v 是 8，返回 5

（1）、二分搜索优化 — 思路

• 假设在[begin，end）范围内搜索某个元素 v，mid == （begin + end）/ 2
  ①、如果v < m，去[begin ， mid）范围内二分搜索
  ②、如果v >= m，去[mid + 1， end）范围内二分搜索
• end指的是数组的长度。
  

（2）、 二分搜索优化 — 实例

import org.junit.Test;
import java.util.Arrays;

public class BinarySearch {
    /**
     * 查找v在有序数组array中待插入位置
     */
    public static int search(int[] array, int v){
        if (array == null || array.length == 0) return -1;

        int begin = 0;
        int end = array.length;
        while (begin < end){
            int mid = (begin + end) >> 1;
            if (v < array[mid]){
                end = mid;
            }else{
                begin = mid+1;
            }
        }
        return begin;
    }

    @Test
    public void test2(){
        int[] array = {2,4,8,8,8,12,14};
        System.out.println(Arrays.toString(array));
        System.out.println(search(array,5) == 2);
        System.out.println(search(array,1) == 0);
        System.out.println(search(array,15) == 7);
        System.out.println(search(array,8) == 5);
    }
}
运行结果：
[2, 4, 8, 8, 8, 12, 14]
true
true
true
true