[数据结构与算法]二分查找问题总结

参考题目

本文参考LeetCode题目如下：

LeetCode 704. 二分查找

LeetCode 35. 搜索插入位置

LeetCode 278. 第一个错误的版本

题目特点

二分查找问题中，题目的共同特点：

• 题目中规定了有序（升序、降序或按种类排序）数组（或字符串），且数组中元素不重复
• 题目要求查找某一目标值，该值可能在上述数组中，也可能不在，如在LeetCode 704. 二分查找、LeetCode 35. 搜索插入位置中，需要确定目标值应在数组中的位置；而在LeetCode 278. 第一个错误的版本中，数组只有两类，且按类排序的元素，题目要求查找第二类元素中的第一个在数组中的位置

解题思路?

二分查找是一种效率较高的查找方法，主要步骤是比较数组（可看作一个区间）中间元素的值与目标值的关系，进而缩小查找区间的大小，最后可判断目标值在数组中的位置，或是否存在于区间中。具体而言：

1.左右双指针及中值指针

首先设置双指针：leftIndex和rightIndex，初始leftIndex指向数组起始位置0，rightIndex指向数组末端位置array.length - 1，再设置一个指针midIndex 来指示区间中间位置，并且赋值：

midIndex = leftIndex?+ (rightIndex?-?leftIndex?) / 2

注意：不要将midIndex赋值方式变为(rightIndex +?leftIndex) / 2，因为该种赋值方式可能导致溢出。

之后比较array[midIndex]值与目标值的大小（或种类等）关系，如果数组是升序排列的，且目标值比array[midIndex]值大，那么就应该缩减（左）区间大小，所以此时leftIndex应该赋值：

leftIndex =?midIndex + 1

同理可得当目标值比array[midIndex]值小时，rightIndex应该赋值：

rightIndex =?midIndex - 1

注意：在大多数情况下都必须以此种方式（指+ 1、- 1操作）进行赋值，否则会导致while循环的循环条件不好写，但有时会出现单边（指leftIndex、rightIndex其中之一）进行+ 1或- 1操作，例如LeetCode 278. 第一个错误的版本，总之，+ 1或- 1操作是必不可少的。

2.while循环

上述过程需写在循环体中，由于循环次数未知，故使用while循环

针对while循环的写法，循环条件会出现leftIndex <=?rightIndex或leftIndex < rightIndex两种情况，需按题意进行具体判断，一般在不确定目标值是否存在于数组中时，写作leftIndex <=?rightIndex，如：LeetCode 704. 二分查找、LeetCode 35. 搜索插入位置，在确定目标值存在于数组中时，写作leftIndex < rightIndex，如LeetCode 278. 第一个错误的版本

3.返回值

按照题目要求设置返回值即可，一般在while循环中也设置了return返回值，表示在数组中找到了目标值