704. Binary Search

标签:xpl   uniq   解法   http   val   style   try   col   entry   

问题:

二分查找,给定一个已排序的数组,和一个目标值target

在该数组中找到target的index返回,若没找到,则返回-1。

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

Note:
You may assume that all elements in nums are unique.
n will be in the range [1, 10000].
The value of each element in nums will be in the range [-9999, 9999].

  

解法:二分查找(Binary Search)

参考 69. Sqrt(x)  的解释部分。

 

代码参考:

 1 class Solution {
 2 public:
 3     int search(vector<int>& nums, int target) {
 4         int l = 0, r = nums.size();
 5         while(l<r) {
 6             int m = l+(r-l)/2;
 7             if(nums[m] == target) return m;
 8             if(nums[m] > target) {
 9                 r = m;
10             } else {
11                 l = m+1;
12             }
13         }
14         return -1;
15     }
16 };

 

704. Binary Search

标签:xpl   uniq   解法   http   val   style   try   col   entry   

原文地址:https://www.cnblogs.com/habibah-chang/p/13489106.html

版权声明:完美者 发表于 2020-08-12 15:53:00。
转载请注明:704. Binary Search | 完美导航

暂无评论

暂无评论...