★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:山青咏芝(shanqingyongzhi)
➤博客园地址:山青咏芝(https://www.cnblogs.com/strengthen/ )
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址:https://www.cnblogs.com/strengthen/p/10403410.html
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
扩展数组:
1 extension Array 2 { 3 //二分法方式1 4 func binarySearch(_ nums:[Int],_ target: Int) -> Int 5 { 6 var low = 0 7 var high = nums.count - 1 8 var mid = (low + high) >> 1 9 10 while low <= high { 11 let val = nums[mid] 12 if target == val { 13 return mid 14 } else if target < val { 15 high = mid - 1 16 } else { 17 low = mid + 1 18 } 19 mid = (low + high) >> 1 20 } 21 return high 22 } 23 24 //二分法方式2 25 func binarySearch(_ nums:[Int],_ start: Int, _ end: Int,_ target: Int) -> Int 26 { 27 let mid = start + (end - start) / 2 28 if nums[mid] >= target && (start == mid || nums[mid - 1] < target) 29 { 30 return mid 31 } 32 if nums[mid] < target 33 { 34 return binarySearch(nums,target, mid + 1, end) 35 } 36 return binarySearch(nums,target, start, mid - 1) 37 } 38 }
测试代码:
1 //注:不含有元素5 2 var arr = [1,2,3,4,6,7,8,9] 3 print(arr.binarySearch(arr,5)) 4 //Print 3 5 print(arr.binarySearch(arr,0,arr.count,5)) 6 //Print 4 7 8 //注:含有元素6 9 print(arr.binarySearch(arr,6)) 10 //Print 4 11 print(arr.binarySearch(arr,0,arr.count,6)) 12 //Print 4