剑指Offer题目笔记19（二分查找）

面试题68：

面试题68

问题：

输入一个排序的整形数组nums和一个目标值t，如果数组nums中包含t，则返回在数组中的下标，否则返回按照顺序插入到数组的下标。

解决方案：

使用二分查找。每次二分查找都选取位于数组中间下标的值，如果目标值等于当前值，返回当前下标。如果目标值大于当前值，那么目标值位于数组后半部分，如果目标值小于当前值，那么目标值位于数组前半部分。

源代码：

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

                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return nums.length;
    }
}

面试题69：

面试题69

问题：

在一个长度大于或等于3的数组中，找到数组最大值对应的下标。

解决方案：

使用二分查找。因为该数组是先递增后递减就像一座山峰，我们要求峰顶的下标，因此需要找到比它左右两边数字都大的数字对应的下标，如果这个数字比它左边的数字大，并且比它右边的数字要小，故峰顶在后半部分，如果这个数字比它左边的数字小，并且比它右边的数字要大，故峰顶在前半部分。

源代码：

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int left = 1;
        int right = arr.length - 2;
        while(left <= right){
            int mid = (left + right) / 2;
            if(arr[mid] > arr[mid+1] && arr[mid] > arr[mid - 1]){
                return mid;
            }

            if(arr[mid] > arr[mid - 1]){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }

        return -1;
    }
}

面试题70：

面试题70

问题：

在一个排序的数组中找出唯一只出现一次的数字。

解决方案：

使用二进制。因为两个相同的数字异或的结果是0，将数组的所有数字进行异或，那么最终结果就是出现一次的数字。
在一个排序的数组中，将数组中的数字两两分组，最初的若干组的两个数字都是相同的，一旦遇到只出现一次的数字之后，后面的组全是不相同的，故出现不同的第一组的第一个数字就是出现一次的数字。
使用二分查找。先找出位于中间的一组，确定该组的两个数字是否相同，如果两个数字相同，那么只出现一次的数字在数组后半部分。如果两个数字不相同，需要继续判断该组是不是第一组，如果是第一组，那么该组的第一个数字就是出现一次的数字。如果不是第一组，那么只出现一次的数字在数组前半部分。

源代码：

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int left = 0;
        int right = nums.length/2;
        while(left <= right){
            int mid = (left + right)/2;
            int i = mid * 2;
            if(i < nums.length - 1 && nums[i] != nums[i + 1]){
                if(mid == 0 || nums[i - 2] == nums[i - 1]){
                    return nums[i];             
                }

                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }

        return nums[nums.length - 1];
    }
}

面试题71：

面试题71

问题：

输入一个正整数数组w，实现一个函数pickIndex根据权重比例随机选择一个下标。

解决方案：

使用二分查找。创建一个和权重数组的长度一样的数组sums，新数组的第i个数值sums[i]是权重数组中前i个数字之和。生成一个随机数p，先选取位于数组中间下标的值，如果p小于当前值，再判断p与前一位的值的大小，如果前一位的值小于等于p，那么返回当前下标，如果p大于当前值，那么权重值在数组前半部分，如果p大于当前值，那么权重值在数组后半部分。

源代码：

class Solution {
    private int[] sums;
    private int total;

    public Solution(int[] w) {
        sums = new int[w.length];
        for(int i = 0;i < sums.length;i++){
            total += w[i];
            sums[i] = total;
        }
    }
    
    public int pickIndex() {
        Random random = new Random();
        int p = random.nextInt(total);
        int left = 0;
        int right = sums.length - 1;
        while(left <= right){
            int mid = (left + right)/2;
            if(sums[mid] > p){
                if(mid == 0 || sums[mid - 1] <= p){
                    return mid;
                }

                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return -1;
    }
}