朝文分享（55）：畅游算法之海（一）——二分查找法

摘要：Binary search, also known as binary search, is an efficient algorithm for finding a specific element in a sorted array. The index

分享兴趣，传播快乐，增长见闻，留下美好！

亲爱的您，这里是LearningYard新学苑。

今天小编为大家带来“畅游算法之海（一）——二分查找法”，欢迎您的访问。

Share interest, spread happiness, increase knowledge, and leave beautiful.

Dear, this is the LearingYard Academy!

Today, Swimming in the sea of algorithms (1) - Binary search ，welcome to visit!

一、认识

1. Understanding

二分查找，也称为折半查找，是一种在有序数组中查找特定元素的高效算法。通过不断逼近目标的中值锁定目标值的下标，其独特的检索方式让数据的查找更加方便快捷。

Binary search, also known as binary search, is an efficient algorithm for finding a specific element in a sorted array. The index of the target value is locked by constantly approaching the median value of the target, and its unique retrieval method makes the search of data more convenient and fast.

二、效果

2. Effect

从网上扒了张图，方便大家理解，上面是二分查找，下面是遍历查找。计算机的运行速度相当快，所有计算left、right和middle的步骤忽略不计，而从数组取出下标对应的值则相对需要较长时间，故将取值的过程算成一步。上下对比，二分查找仅需3步，而遍历查找需要11步。

I picked a picture from the Internet to facilitate everyone's understanding. The above is binary search, and the following is traversal search. The computer is so fast that all the steps to compute left, right, and middle are ignored, and it takes a relatively long time to get the index from the array, so the process of getting the value is counted as one step. For comparison, binary search takes only three steps, while traversal search takes 11.

三、实现

3. Implementation

力扣中的编号704就是一道关于二分查找的题。

The number 704 in the force buckle is a question about binary search.

要编写的Solution类下的一个公共函数，二分查找函数。参数有一个整型数组和一个目标值。二分查找法的核心就是中值，即nums[middle]。找到中值就需要确定区间，所以还有两个参数，left和right。这两个参数去确定查找区间和中值。初始区间是整个数组。

We're going to write a public function under the Solution class, the binary search function. Arguments have an array of integers and a target value. At the heart of binary search is the median value, or nums[middle]. Finding the median requires determining the interval, so there are two more parameters, left and right. These two parameters determine the search range and median. The initial range is the entire array.

通过不断地缩小区间，使中值不断逼近目标值。先看循环里面，循环一次，区间缩小一次，中值逼近一次。区间缩小一次：判断中值与目标值的关系，选择改变left还是right；中值逼近一次：在循环的最前面或者最后面，要对中值进行修改。但由于前面middle初始化为0，所以这里只能放在循环的最前面。

By continuously narrowing the interval, the median value keeps approaching the target value. Let's look at the inside of the loop. Once through the loop, the interval shrinks once, and the median approaches once. Narrow the interval once: determine the relationship between the median value and the target value, and choose to change the left or right. Median approximation once: At the beginning or end of the loop, the median is modified. But since middle is initialized to 0, it has to be placed first in the loop.

然后，while的目的是二分查找完后没有找到，跳出循环，返回-1。为什么呢？假设最后的区间中就只有一个元素了，此时，left、middle和right都是同一个值，且该元素并不是目标值。那么会发生什么？left加一或right减一。这样一来，left就不小于等于right了，说明已经查找完了，且没有找到。

Then, the purpose of while is to break out of the loop and return -1 when the binary search is complete and no binary search is found. Why? Suppose there is only one element left in the final range, in which case left, middle, and right are all the same value, and that element is not the target value. So what happens? Add one to the left or subtract one from the right. Now left is not less than or equal to right, which means we're done looking and we didn't find it.