Question

折半查找对查找的有序序列有什么要求有什么要求

折半查找对查找的有序序列有什么要求有什么要求

Answer 1

折半查找必须要求待查找的序列有序。

假设对于递增序列（递减序列反之），mid 为序列的中间位置，将序列分成两个部分，折半查找首先会将待查找值 value 与序列中间的值 list[mid] 进行比较，有三种情况：

1. value == list[mid]，找到了，直接返回 mid

2. value > list[mid]，说明待查找值 value 可能在右半部分

1. 将 mid 改为右半部分的中间值
   

3. value < list[mid]，说明待查找值 value 可能在左半部分

1. 将 mid 改为左半部分的中间值

Answer 2

要求如下：
1、待查找序列有序（关键字递增或者递减有序）
2、顺序存储（也就是数组连续存放，便于按下标或者序号随机访问）