二分查找算法

Question

如题所述

Answer 1

二分查找算法，该算法要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。如果一个序列是无序的或者是链表，那么该序列就不能使用二分查找。

二分查找算法原理：若待查序列为空，则返回-1，并退出算法；若待查序列不为空，则将它的中间元素与目标数值进行比较，判断是否相等；若相等，则返回中间元素索引，并退出算法；此时已查找成功。若不相等，则比较中间元素与目标数值的大小。

若中间元素>目标数值，则将当前序列的前半部分作为新的待查序列；若中间元素<目标数值，则将当前序列的后半部分作为新的待查序列；在新的序列上重新从第（1）步开始查找。

二分法查找的思路：首先，从数组的中间元素开始搜索，如果该元素是目标元素，则搜索过程结束，否则执行下一步。如果目标元素大于/小于中间元素，则在数组大于/小于中间元素的那一半区域查找，然后重复步骤（1）的操作。如果某一步数组为空，则表示找不到目标元素。

二分查找的一个技巧是：不要出现else，而是把所有情况用else，if写清楚，这样可以清楚地展现所有细节。本文都会使用else，if，旨在讲清楚，读者理解后可自行简化。