[数据结构与算法]查找算法-----＞二分法

二分法主要是针对 有序数组使用
列如

步骤：

1. 首先，找到数组的中间点，从数组中间元素开始搜索，如果是该元素则结束搜索，不是则执行下一步。
2. 如果目标元素大于该中间元素，则在数组大于中间元素的那一半区域查找，然后重复步骤（1）的操作。
3. 如果目标元素小于该中间元素，则在数组小于中间元素的那一半区域查找，然后重复步骤（1）的操作。
4. 重复步骤（2）（3）（1）直到找到元素或者left >right 推出循环没有找到。

时间复杂度为O（logn）

    public int binarySearch(int []arr,int key){
        int left=0,right=arr.length-1;
        //循环条件
        while (left<=right){
            //为了防止大数
            int mid=left+(right-left)/2;
            if(arr[mid]==key){
                return arr[mid];
            }else if(arr[mid]>key){
                //中间数组太大了 ，key在小的一边
                right=mid-1;
            }else if (arr[mid]<key){
                //中间数组太小了，key在大的一边
                left=mid+1;
            }
        }
        //循环出来没有找到
        return -1;
    }

下面来看两道剑指Offer的题：
【剑指 Offer 53 - II. 0～n-1中缺失的数字】

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
示例 1:

输入: [0,1,3]
输出: 2 示例 2:

输入: [0,1,2,3,4,5,6,7,9]
输出: 8

class Solution {
    public int missingNumber(int[] nums) {
        int i = 0, j = nums.length - 1;
        while(i <= j) {
            int m = (i + j) / 2;
            if(nums[m] == m) i = m + 1;
            else j = m - 1;
        }
        return i;
    }
}

剑指 Offer 53 - I. 在排序数组中查找数字 I

统计一个数字在排序数组中出现的次数。

示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: 0

class Solution {
    public int search(int[] nums, int target) {
        return helper(nums, target) - helper(nums, target - 1);
    }
    int helper(int[] nums, int tar) {
        int i = 0, j = nums.length - 1;
        while(i <= j) {
            int m = (i + j) / 2;
            if(nums[m] <= tar) i = m + 1;
            else j = m - 1;
        }
        return i;
    }
}