浅谈-二分查找-数据结构

一、什么是二分查找？

1.二分查找又称折半查找，它是一种效率较高的查找方法。

2.二分查找要求：（1）必须采用顺序存储结构 （2）.必须按关键字大小有序排列

3.原理：将数组分为三部分，依次是中值（所谓的中值就是数组中间位置的那个值）前，中值，中值后；将要查找的值和数组的中值进行比较，若小于中值则在中值前 面找，若大于中值则在中值后面找，等于中值时直接返回。然后依次是一个递归过程，将前半部分或者后半部分继续分解为三部分。

4.实现：二分查找的实现用递归和循环两种方式

二、举例说明

1、我们首先引入这样一个问题：如果规定某一科目成绩分数范围：[0,100]，现在小明知道自己的成绩，他让你猜他的成绩，如果猜的高了或者低了都会告诉你，用最少的次数猜出他的成绩，你会如何设定方案？（排除运气成分和你对小明平时成绩的了解程度）

①最笨的方法当然就是从0开始猜，一直猜到100分，考虑这样来猜的最少次数：1（运气嘎嘎好），100（运气嘎嘎背）；

②其实在我们根本不知道对方水平的条件下，我们每一次的猜测都想尽量将不需要猜的部分去除掉，而又对小明不了解，不知道其水平到底如何，那么我们考虑将分数均分，

将分数区间一分为2，我们第一次猜的分数将会是50，当回答是低了的时候，我们将其分数区域从【0,100】确定到【51,100】；当回答高了的时候，我们将分数区域确定到【0,49】。这样一下子就减少了多余的50次猜想（从0数到49）（或者是从51到100）。

③那么我们假设当猜完50分之后答案是低了，那么我们需要在【51,100】分的区间内继续猜小明的分数，同理，我们继续折半，第二次我们将猜75分，当回答是低了的时候，我们将其分数区域从【51,100】确定到【76,100】；当回答高了的时候，我们将分数区域确定到【51,74】。这样一下子就减少了多余的猜想（从51数到74）（或者是从76到100）。

④就此继续下去，直到回复是正确为止，这样考虑显然是最优的

假设数组array为[7,10,13,16,19,29,32,33,37,41,43],要查找的元素为11：

2018060320181268.png

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