swift写二分法查找

一、原理

1.二分法查找的前提是要先将数组进行排序

2.二分法查找是将数组逐次分成两个数组,然后再在分好的两个数组当中的一个进行继续分数组查找的一个过程,所以二分法查找只会查找数组当中的一部分。

3.比较。如果要查找的元素大于数组分割的中间元素,那么查找就在后面的大的数组中进行,如果要查找的元素小于数组的分割的中间元素,那么查找就在前面的小数组中进行,当然如果正好等于的话那么查找就结束了。

4.话不多说,直接上代码

func binarySearch(array: [Int], target: Int) -> Int {

 var left = 0
 var right = array.count - 1

 while (left <= right) {

   let mid = (left + right) / 2
   let value = array[mid]

   if (value == target) {
     return mid
   }

  if (value < target) {
    left = mid + 1
  }

   if (value > target) {
      right = mid - 1
   }
  }

  return -1
}

5.上面的这种写法只适用于整型数组,我们是要查找所有可以进行比较的元素类型,所以这里要用到泛型

func binarySearch(array: [T], target: T) -> Int  {

  var left = 0
  var right = array.count - 1

  while (left <= right) {

    let mid = (left + right) / 2
    let value = array[mid]

    if (value == target) {
      return mid
    }

    if (value < target) {
      left = mid + 1
    }

    if (value > target) {
      right = mid - 1
    }
  }

  return -1
}

6.当然也还有一些其他的扩展,比如你想在字符串数组中查找以某串字符开头的元素也是可以的

func binarySearchPrefix(array: [String], target: String) -> Int {

  var left = 0
  var right = array.count - 1

  while (left <= right) {

    let mid = (left + right) / 2
    let value = array[mid]

    if (value.hasPrefix(target)) {
      return mid
    }

    if (value < target) {
      left = mid + 1
    }

    if (value > target) {
      right = mid - 1
    }
  }

   return -1
}

到此,二分法基本上也就差不多了

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • Swift的二分法查找实践 在这篇教程中我们会使用计算机科学里一个基础的算法:二分法查找binary search...
    不是谢志伟阅读 1,969评论 1 5
  • 清晨五点,习惯性的醒来,窗外早起的鸟儿时不时的啼鸣两声。活动舒展下身体,半小时的瑜伽,让昨天在太阳下暴晒了十多个小...
    清姀一一阅读 566评论 10 9
  • 阅读的书:《一切情感问题的答案——冷眼观爱2》 阅读时间:60分钟 阅读感受:这本书简直就是写给女性的脱单秘籍,原...
    玉虹阅读 188评论 0 0
  • 周末轻松的时光,有没有和家人、朋友喝上一杯呢? 是不是觉得有必要去证明下自己有了一个新的习惯-喝酒呢?(莫名其妙的...
    忧喜阅读 522评论 0 0
  • 今天加班到现在,回家估计没时间学习画画了,我就暂且用在公司用水笔当铅笔画的贴上了看看吧
    多可爱_Cutie阅读 266评论 0 3