[LeetCode] 704. Binary Search

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

Constraints:

1 <= nums.length <= 104
-104 < nums[i], target < 104
All the integers in nums are unique.
nums is sorted in ascending order.

二分查找。

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-search
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这个题跟35题几乎一样。思路就是二分，没什么可说的，但是注意二分查找有好几种模板，我这里给出我比较喜欢的一种。当while条件是带等号的时候，且当nums[mid] < target的时候，因为知道mid及其左边都小于target，所以left可以从mid的右边（mid + 1）开始继续查找，同理right也是从mid的左边开始查找，即right = mid - 1。

同时我解释一下 while (left <= right) 的终止条件是 left == right + 1，写成区间的形式就是 [right + 1, right]，或者带个具体的数字进去 [3, 2]，可见这时候区间为空，因为没有数字既大于等于 3 又小于等于 2 的吧。所以这时候 while 循环终止是正确的，直接返回 -1 即可。

时间O(logn)

空间O(1)

Java实现一

 1 class Solution {
 2     public int search(int[] nums, int target) {
 3         int left = 0;
 4         // 注意right的定义，是数字的最后一个元素的下标
 5         int right = nums.length - 1;
 6 
 7         // 搜索的范围都在数组的下标范围内
 8         // 如果nums[mid]不是目标值，下标一定要 +/- 1
 9         // 注意left <= right
10         while (left <= right) {
11             int mid = left + (right - left) / 2;
12             if (nums[mid] == target) {
13                 return mid;
14             } else if (nums[mid] < target) {
15                 left = mid + 1;
16             } else {
17                 right = mid - 1;
18             }
19         }
20         return -1;
21     }
22 }

Java实现二

 1 class Solution {
 2     public int search(int[] nums, int target) {
 3         int left = 0;
 4         // right也可以是开区间，[left, right)
 5         // 此时right在数组下标范围之外
 6         int right = nums.length;
 7         while (left < right) {
 8             int mid = left + (right - left) / 2;
 9             if (nums[mid] == target) {
10                 return mid;
11             } else if (nums[mid] > target) {
12                 // 因为right是开区间所以只能移动到mid
13                 right = mid;
14             } else {
15                 left = mid + 1;
16             }
17         }
18         return -1;
19     }
20 }

JavaScript实现

 1 /**
 2  * @param {number[]} nums
 3  * @param {number} target
 4  * @return {number}
 5  */
 6 var search = function(nums, target) {
 7     // corner case
 8     if (nums == null || nums.length == 0) {
 9         return -1;
10     }
11 
12     // normal case
13     let left = 0;
14     let right = nums.length - 1;
15     while (left <= right) {
16         let mid = Math.floor(left + (right - left) / 2);
17         if (nums[mid] == target) {
18             return mid;
19         } else if (nums[mid] < target) {
20             left = mid + 1;
21         } else {
22             right = mid - 1;
23         }
24     }
25     return -1;
26 };