算法-二分查找

二分查找

什么是二分查找：

• 前提是线性表中的记录必须是关键码有序(通常从小到大有序),线性表必须采取顺序存储。
• 基本思想：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；
• 若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；
• 若给定值大于中间记录的关键字，则在中间记录的左半区继续查找；
• 若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。
• 不断重复上述过程，查到查找成功，或所有查找区域无记录，查找失败为止

public static int find(int[] arr,int num){
    if(arr == null || arr.length == 0){
        return -1;
    }
    int L = 0;
	int R = arr.length - 1;
	while (L <= R) { //边界条件：最少有一个数
		//int mid = (L + R) / 2;
        int mid = L + ((R - L) >> 1);  //防止加法溢出
		if (arr[mid] == num) {
		 	return mid;
		} else if (arr[mid] < num) {
			L = mid + 1;
		} else {
			R = mid - 1;
	 	}
 	}
    return -1;
}

---

常规算法题

1.在一个有序数组中，找 <= 某个数最右侧的位置

• 思路：

  1. 设定一个index，默认位置是L
  2. 设定一个mid，默认位置是(L+R)/2
  3. 对mid和val进行判断
     1. mid <= val,说明mid当前位置在val左侧，index=mid，同时R=mid-1，缩小范围
     2. mid > val,说明mid当前位置在val左侧，那就需要L=mid+1，缩小范围
  4. L<=R,表明边界条件是只有一个数，这个时候的mid如果满足mid <= value，那就是最右侧的index = mid，不然，直接返回index

  public static int nearestIndex(int[] arr,int value){
      int L = 0;
      int R = arr.length - 1;
      int index = L;
      if(arr[L] <)
      while(L <= R){
          int mid = L + ((R-L) >> 1);
          if(arr[mid] <= value){
              index = mid;
              L = mid +1;
          } else{
              R = mid - 1;
          }
      }
      return index;
  }
  

  ---

2.局部最小值问题

题目描述：

​ 查询一个数组的任意一个局部最小值(0坐标 < 右面 0就是局部最小 , length - 1 < length - 2 length - 1 就是局部最小),中间值是小于左面也小于右面, 数组无序,并且相邻两个数一定不相等

• 思路：
  1. 如果这个数组左边界和有边界满足局部最小，那就直接返回左边界或者有边界
  2. 如果这个数组左边界和有边界不满足局部最小，那就说明左面是向下趋势，右面是向上趋势，那中间必然有一个或多个局部最小值。
  3. 那就用二分法进行查询，设定一个参数mid，初始值是$(L + R)/2$
  4. 对mid的左右两侧趋势进行判断
     1. arr[mid] > arr[mid - 1]，表明mid的左边区域是向上趋势，又因为数组的左侧区域是向下趋势，那局部最小值必然在mid的左侧，R = mid - 1；
     2. arr[mid] > arr[mid + 1],表明mid的右侧区域是向下趋势，又因为数组的右测区域是向上趋势，那局部最小值必然在mid的右侧，L = mid + 1；
     3. 找到结束循环的边界条件，这里采用left<right,极限情况是两个数的时候，如果遇到极限情况的时候，即使比较香玲两个数的情况，比较的也是left的值是否满足局部最小，那肯定是满足的，因此，极限情况是两个数的时候，直接返回left，即可。

public static int nearestIndex(int[] arr, int value) {
    if(arr == null || arr.length == 0){
        return -1;
    }
    if(arr.length = 1 || arr[0] < arr[1]){
        return 0;
    }
    if(arr[arr.length - 1] <arr[arr.length - 2]){
        return arr.length - 1;
    }
    int left = 1;
    int right = arr.length - 2;
    int mid = 0;
    while(left < right){
        mid = left + ((right - left) >> 1);
        if(arr[mid] > arr[mid - 1]){
            right = mid - 1
        } else if (arr[mid] > arr[mid + 1]){
            left = mid + 1;
        } else {
            return mid;
        }
    }
    return left;
}