三种排序三种查找

冒泡

快速排序

二分法查找 -scala

建立在有序的条件下

二叉树查找

前提条件

如何保证下标的有效性 （奇数+偶数）/2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def binarySearch(arry:Array[Int], needed:Int):Int={
  var left = 0
  var right = arry.length -1
  while(left < right) {
    val mid:Int = (right - left)/2 + left
    needed   match {
      case _ if needed > arry.apply(mid) => left = mid
      case _ if needed < arry.apply(mid) => right = mid
      case _ if needed == arry.apply(mid) => return mid + 1
    }
  }
  return -1
}

红黑树遍历

二叉树遍历