查找算法

一、顺序查找（Linear Search）

顺序查找，利用朴素的想法，简单的从数组头开始搜索希望找到的元素。算法逻辑可以概括为：

从数组的第一个元素开始，依次往下比较，直到找到要找的元素为止。

用一个简单的程序举例

int main(){
  int  k, x;
  int array[] = {2, 3, 1, 7, 5, 8, 9, 0, 4, 6};
  cout << "请输入要查找的元素值："; 
  cin >> x;
  for (k = 0; k < 10; ++k){
      if(x == array[k]) {
          cout << k;
          break;
      }
      if(k == 10) 
          cout << "not found";
  }
  return 0;
}

二、二分查找

二分查找要求数组元素按照某一顺序排序，如数字的大小顺序、字母的字母序等。一般在查字典的时候，就会使用类似二分查找的思想。二分查找的基本步骤有三步：

1. 确定上下界：lh, rh

2. 找出中间元素的位置：mid = ( lh + rh ) / 2

3. 比较中间元素与欲查找的元素 key，根据不同情况进入不同分支继续处理

   • 如key 等于中间元素，则mid就是要查找的元素的位置

   • 如key >中间元素，则从lh–mid的这些元素不可能是要查找的元素，修正查找范围为lh= mid + 1到rh

   • 如key <中间元素，则从mid - rh的这些元素不可能是要查找的元素，修正查找范围为lh到rh = mid - 1

   • 如lh > rh，则要查找的元素不存在

int main() {
    int lh, rh, mid, x; 
    int array[]={0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; 
    cout << "请输入要查找的数据："; 
    cin >> x; 
    lh = 0; rh = 9; 
    while ( lh <= rh ) { 
    	mid = ( lh + rh ) / 2; 
    	if ( x== array[mid] ) { 
    		cout << x << "的位置是：" << mid << endl; 
    		break; 
        } 
        if ( x < array[mid]) rh = mid - 1; 
        else lh = mid + 1; 
    } 
    if (lh > rh) cout << "没有找到" << endl; 
    return 0; 
}

算法性能

显然二分查找的效率比顺序查找要高，二分查找在最坏情况下查找次数为log₂N+1次，而顺序查找最坏情况查找次数则为N次。但二分查找只能对已排序数组操作，这是其局限性。