有序数组之二分查找

落日映苍穹つ 2022-07-21 00:17 183阅读 0赞

## 数据结构与算法是程序深入设计需要理解的知识。关于数据结构和算法就从最简单的部分开始了。来看第一个问题:数组的二分查找。 ##

### 数组是我们常见的数据结构，在程序设计中应用广泛。关于数组的操作通常是：查找、插入、删除。二分查找是我们常用的一种查找方式，效率比较高。提到二分查找，最原始的方式是线性查找。线性查找就是直接在有序数组的基础上直接从左向右方向进行查找，当在数组中找到一个比一个待查数据大时就退出查找。相比线性查找，二分查找优势明显。 ###

### 二分查找：折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表。 ###

![这里写图片描述][20160710205639003]

### 上图显示了二分查找的过程。有序数组边界分别是lowerBound、upperBound。首先取中点，curIn=（lowerBound+upperBound）/2。这样就有了第一次比较判断curIn与待查数据的大小，若待查数据较大，就只用对后面一部分进行查找了。此时lowerBound=curIn+1；再重新计算中点，这样一直比较下去，直到限定为一个数据或直到查找到这个数据。 ###

### 来看代码： ###

public int find(long searchKey)
          {
          int lowerBound = 0;
          int upperBound = nElems-1;
          int curIn;
          while(true)
           {
              curIn = (lowerBound + upperBound ) / 2;
              if(a[curIn]==searchKey)
                 return curIn;             
               else if(lowerBound > upperBound)
                return nElems;          
                else                        
                  {
                    if(a[curIn] < searchKey)
                    lowerBound = curIn + 1; 
                  else
                    upperBound = curIn - 1; 
                }  
             }  
          }

### 二分查找find方法中返回查找数组下标。这样查找比线性查找快。 ###

### 数组长度与最多查找次数的关系 ###

### 假定数组长度是N，那么假设在最坏情况下二分查找所需要比较的次数是log2（N），也就是说当数组长度是10时，所需要比较次数是4 ，100需要比较的次数是7。用大O表示法表示线性查找运行时间是O(N),二分查找的运行时间是O(logN)。 ###

### 考虑到二分查找的弊端是在有序数组的基础上进行查找的。因此排序是必不可少的一个步骤。 ###

[20160710205639003]: /images/20220720/d147730af50349ca97bbab5624e6c24a.png