二分搜索

• 如何确定一个元素在数组中的位置?
• 如果是无序数组,从第 0 个位置开启式遍历搜索,平均时间复杂度
• 如果是有序数组,可以使用二分搜索,最坏时间复杂度为

思路

• 假设在[begin,end) 范围内搜索某个元素 v, mid = (begin + end) / 2 , 这里 end 取的是数组长度
• 如果 v < m, 去[begin, mid)范围内二分搜索
• 如果 v > m, 去[mid+1, end)范围内二分搜索

• 如果 v = m, 直接返回 mid

  
  image.png

实现

• 查找某个元素在有序数组中的位置,如果没有返回-1

int indexOf(List<int> array, int v) {
  if (array == null || array.length == 0) return -1;
  int begin = 0, end = array.length;
  while(begin < end) {
    int mid = (begin + end) >> 1;
    if (v < array[mid]) {
      end = mid;
    } else if (v > array[mid]) {
      begin = mid + 1;
    } else {
      return mid;
    }
  }
  return -1;
}

• 查找某个元素在有序数组中待插入的位置

int search(List<int> array, int v) {
  if (array == null || array.length == 0) return 0;
  int begin = 0, end = array.length;
  while(begin < end) {
    int mid = (begin + end) >> 1;
    if (v < array[mid]) {
      end = mid;
    } else {
      begin = mid + 1;
    }
  }
  return begin;
}

问题

• 如果存在多个相同的值,返回的索引是哪一个? 返回的是不确定的