二分查找算法 - 0～n-1中缺失的数字【简单-LeetCode】

雨点打透心脏的1/2处 2022-12-06 05:29 126阅读 0赞

地址：[https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/][https_leetcode-cn.com_problems_que-shi-de-shu-zi-lcof]  
题目描述：  
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

示例：

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

### 解题思路： ###

>     这是一个典型的二分查找算法的运用。将所要査找的序列的中间位置的数据与所要査找的元素进行比较，如果相等，则表示査找成功，否则将以该位置为基准将所要査找的序列分为左右两部分。  
>     根据所要査找序列的升降序规律及中间元素与所查找元素的大小关系，来选择所要査找元素可能存在的那部分序列，对其采用同样的方法进行査找，直至能够确定所要查找的元素是否存在  
> 二分查找算法(折半查找 Binary Search)  
>     前提条件：要求线性表必须采用**顺序存储结构**，且表中元素**按关键字有序排列**(有序)

代码：

public class Demo { 
    
        public static int errorNumber(int []nums){ 
            //排序过的数组，一个个查询
            int low = 0,high = nums.length - 1,middle;
    
            while(low <= high){ 
                middle = (low + high) / 2;
                if(nums[middle] == middle){ 
                    //相等，则前面没有缺失，往后查询
                    low = middle + 1;
                }else { 
                    //不相等，证明前面有缺失，往前查询
                    high = middle -1;
                }
            }
            return low;
        }
        
        public static void main(String[] args) { 
            int []num = { 0,1,2,3,5,6};
            System.out.println(errorNumber(num));
        }
    
    }

[https_leetcode-cn.com_problems_que-shi-de-shu-zi-lcof]: https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/