数组-二分查找

数组的特点

1. 长度固定且可知

2. 访问数组中的某个元素的时间复杂度为 O(1), 可通过index直接访问

3. 在数组中插入或删除一个元素，时间复杂度为O(n)，因为需要先查询

二分查找

前提： 数值按照index排序，如此index与值就有了一致升序或反之，就可以利用这个特点减少查找的范围

            为顺序存储结构, 标明index连续，则值连续

算法：递归

     func int binarySearch(int nums[], int target): 

            start = 0, end = nums.length

            mid = start +  (end - start) / 2;

            while (start + 1 < end)

                   if nums[mid] == target: return mid

                   if nums[mid] < target: start = mid

                   if nums[mid] > target: end= mid

            if nums[start] == target: return start;

            if nums[end] == target: return end;

            return -1;

时间复杂度： O(logN)

空间复杂度:  O(logN)