[Swift]LeetCode704.二分查找|BinarySearch

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10505849.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Given a sorted (in ascending order) integer array nums of nelements and a target value, write a function to search target in nums. If target exists, then return its index, otherwise return -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].

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

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：

你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

292ms

 1 class Solution {
 2     func search(_ nums: [Int], _ target: Int) -> Int {
 3         
 4         var left = 0
 5         var right = nums.count - 1
 6         var mid = (left + right) / 2
 7         
 8         while left <= right {
 9             if target == nums[mid] {
10                 return mid
11             } else if target == nums[left] {
12                 return left
13             } else if target == nums[right] {
14                 return right
15             } else if target > nums[left] && target < nums[mid] {
16                 right = mid - 1
17                 mid = (left + mid) / 2
18                 left += 1
19             } else if target > nums[mid] && target < nums[right] {
20                 left = mid + 1
21                 mid = (mid + right) / 2
22                 right -= 1
23             } else {
24                 return -1
25             } 
26         }
27         
28         return -1
29     }
30 }

Runtime: 296 ms

Memory Usage: 18.9 MB

 1 class Solution {
 2     func search(_ nums: [Int], _ target: Int) -> Int {
 3         var low = 0
 4         var high = nums.count - 1
 5         var mid = (low + high) >> 1
 6         
 7         while low <= high {
 8             let val = nums[mid]
 9             if target == val {
10                 return mid
11             } else if target < val {
12                 high = mid - 1
13             } else {
14                 low = mid + 1 
15             }
16             mid = (low + high) >> 1
17         }
18         return -1
19     }
20 }

312ms

 1 class Solution {
 2     func search(_ nums: [Int], _ target: Int) -> Int {
 3         if nums.count == 1 {return nums[0] == target ? 0 : -1}
 4         else if nums.count == 0 {return -1}
 5         
 6         return binarySearch (nums, target, 0, nums.count-1)
 7     }
 8     
 9     func binarySearch(_ nums:[Int], _ target: Int, _ l: Int, _ r: Int) -> Int {
10         if (r >= l) {
11             var mid = l + (r-l)/2
12             if nums[mid] == target {return mid}
13             else if nums[mid] > target {return binarySearch(nums, target, l, mid-1) }
14             else {return binarySearch(nums, target, mid+1, r)}
15         }
16         return -1
17     }
18 }

352ms

 1 class Solution {
 2     
 3     var start = 0;
 4     var end = 0;
 5     
 6     var center: Int {
 7         return (end + start) >> 1
 8     }
 9     
10     func search(_ nums: [Int], _ target: Int) -> Int {
11         end = nums.count
12         while start != end - 1 {
13             if nums[center] == target {
14                 return center
15             }else if nums[center] < target  {
16                 start = center
17             }else {
18                 end = center
19             }
20         }
21         return nums[center] == target ? center : -1
22     }
23 }

452ms

 1 class Solution {
 2     func search(_ nums: [Int], _ target: Int) -> Int {
 3         func search(_ l: Int, _ r: Int) -> Int {
 4             if l == r && nums[l] != target {
 5                 return -1
 6             }
 7             
 8             let mid = l + (r + 1 - l) / 2
 9             
10             if nums[mid] == target {
11                 return mid
12             } else if nums[mid] > target {
13                 return search(l, mid - 1)
14             } else {
15                 return search(mid, r)
16             }
17         }
18         
19         return search(0, nums.count - 1)
20     }
21 }