本文共 4555 字，大约阅读时间需要 15 分钟。

查找算法——二分查找

1. 简介：有序数列，进行折中查找
2. 思路分析：
   • 确定该数组的中间下标，mid = (left + right) / 2
   • 然后将需要查找的数与中间值mid进行比对
     - 比中间值大，那就再以中间值mid为left，right为right进行同样的折半查找
     - 比中间值小，那就再以中间值mid为right，left为left进行同样的折半查找
   • 如果arr[mid] == findVal,说明找到了
   • 判定递归截至的条件
     - 找到对应的值，返回后进行推出
     - 没有找到对应的数值，会满足left>right，然后进行退出
3. 代码实现：
   我的代码：

package binarysearch;public class Binary {
       public static void main(String[] args) {
           int[] arr = {
   1,3,45,56,789,888,999};        System.out.println(binarySearch(arr,0,arr.length - 1,4));    }    static int valIndex = - 1;    public static int binarySearch(int[] arr,int left,int right,int searchVal){
           //设置中间值的索引        int mid = (left + right) / 2;        if(left < right){
             if(arr[mid] == searchVal){
               //如果找到对应的值,那就退出            valIndex =  mid;          }else if(arr[mid] > searchVal){
               //如果你要找的值小于中间值,那就说明在左半边            binarySearch(arr,left,mid - 1,searchVal);          }else if (arr[mid] < searchVal){
               //如果你要找的值大于中间值,那就说明再右半边            binarySearch(arr,mid + 1,right,searchVal);          }else{
               valIndex =  - 1;          }          return valIndex;        }    }}

问题分析：

1. 每一次都折中是否能够查遍每一个元素？

• 通过实验发现，不能够查找随后一个元素。这取决去整除的特性，自动舍弃余数。如果是相邻的两个数，他会下意识的取左边那个数，而右边的数取不到。如{1，3}，取中间值，会默认是索引0，就是对应的1.永远取不到三

2. 如果在运算中没有对中值索引进行更改，为什么找不到元素时会陷入死循环？
   *

• 如{1，3}，要寻找的是2。因为不专门对mid进行改变，mid在仅仅剩两个值的时候始终不变，都是0，right右边界始终不变，都是1，所以陷如【0，1】的死循环
• 问题：不修改前，能够对除了最后一个元素的所有数组元素进行遍历，但是对于不在数组内的元素，会现如相邻区间的死循环。
• 修改：既然每一次比较都是和中间值进行比较，那既然不等与中间值，那么在下一次比较中就可以不把中间值算在内。比中间值小，那么在下一次比较中，right = mid - 1，比中间值大，下一次比较 left = mid + 1。既可以便利最后一个元素，又可以避免陷入死循环，最后一定是left == right。
• 问题：在查找不存在的数时，会陷入死循环。最后肯定是围绕着某一个值来回反复旋转。因为无论是加一，还是减一，最终都是left和mid以及mid等于同一个数。
  
• 修改：添加判断是否执行的条件，一但left和right并于0处，就会出现right = -1，left = 0，然后陷入死循环。所以前提就必须是，left <right才可以

教程代码：

public static int binarySearch(int[] arr,int left,int right,int searchVal){
           //设置中间值的索引        int mid = (left + right) / 2;        if (right >= left){
               if(arr[mid] == searchVal){
                   //如果找到对应的值,那就退出                return mid;            }else if(arr[mid] > searchVal){
                   //如果你要找的值小于中间值,那就说明在左半边                return binarySearch(arr,left,mid - 1,searchVal);            }else if (arr[mid] < searchVal){
                   //如果你要找的值大于中间值,那就说明再右半边                return binarySearch(arr,mid + 1,right,searchVal);            }        }        return -1;    }

分析总结：

1. 没有必要设置static index专门承装索引值，直接设置返回的是递归函数返回的值就可以了，层层递归，返回的一定是迭代到最终的那个数。返回最终值
2. 思考不够有逻辑，两数相比较，除了大于，等于，小于，还剩什么？第四种使你变得吗？大哥！！！

改良版——有序数组中多个相同的值

1. 思路分析：找到mid的索引之后并不要立即放回，而是以mid为中心分别向两边进行扫描，将所有于mid相同的值的索引加入到集合ArrayList中，然后将集合ArrayList返回
2. 代码实现：

public static List
   
     binarySearch2(int[] arr,int left,int right,int searchVal){
           //区别一下重写和重载:重载:两同一不同,同类同名,不同的形参.重写:原方法的覆盖,是子类对父类的继承.        //这里都不是,形参列表不同,只有返回值类型不同,不是重载,没有继承,不是重写        int mid = (left + right) / 2;        if (left <= right){
               if (searchVal < arr[mid]){
                   return  binarySearch2(arr,left,mid - 1,searchVal);            }else if(searchVal > arr[mid]){
                   return binarySearch2(arr,mid + 1,right,searchVal);            }else{
                   List
    
      list = new ArrayList<>();                int temp = mid;                while (temp >= 0 && arr[temp] == arr[mid]){
                       list.add(temp);                    temp --;                }                temp = mid + 1;                while (temp <= arr.length - 1 && arr[temp] == arr[mid]){
                       list.add(temp);                    temp ++;                }                return list;            }        }        return new ArrayList<>();    }
    
   

分析总结：

1. 多重索引关键在于遍历，因为是有序数组，所以相同的一定在一起。对其左右进行遍历就行了。
2. 出现两个数组复制值的情况，赋值加上索引移位两步走

一年之后

乍一看，还是很纳闷的，二分查找用得着用递归吗？不过递归好像确实很好看，而且代码很简单。自己写的是啥？怎么会犯这种逻辑错误，除了大于，还有小于，然后就是等于，不知道第四种怎么编出来的。

没有仔细看自己以前写的，再次为同样的事件感到疑惑，两个数，求不出右边那个是因为没有加上左界等于右界的条件

C语言版（非递归）

#include 
   
    #include 
    
     int BinSearch(long num[],long x, int n);int main(){
       long num[] = {
   0,1},goal = 1;    int index = BinSearch(num,goal,2);    printf("index：%d",index);    return 0;}int BinSearch(long num[],long x, int n){
       int low = 0 , high = n - 1 , mid;    while(low <= high)    {
           //注意上面的判定条件一定是等号        if(num[high] == x)        {
               return high;        }        mid = (low + high) / 2;        if(num[mid] == x)        {
               return mid;        }        else if(num[mid] < x)        {
               high = mid - 1;        }        else        {
               low = mid + 1;        }    }    return -1;}
    
   

转载地址：http://uqgpb.baihongyu.com/