3月22日二分法查找

二分查找：

二分查找也叫折半查找，二分查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

普通查找的时间复杂度为O（n）,二分查找的时间复杂度仅需要O（log2^n）

查找的实现原理：先定左右边界，之后比较待查找元素与中间元素谁大谁小，如果中间值大于目标值，那么右边界等于中间mid-1;如果中间值小于目标值，那么左边界left=mid+1；

代码实现

int main() {
	int n;
	scanf("%d", &n);
	int* nums = (int*)malloc(sizeof(int) * n);
    if(nums==NULL)return 0;
	for (int i = 0; i < n; i++) {
		scanf("%d", &nums[i]);
	}
	int left = 0, right = n - 1;
	int target;
	scanf("%d", &target);
	while (left <= right) {
		int mid = (right - left) / 2 + left;
		if (nums[mid] > target) {
			right = mid - 1;
		}
		else if (nums[mid] < target) {
				left = mid + 1;
		}
		else {
			printf("%d", mid);
		}

	}
    free(nums);
	return 0;
}

注意事项

• 1.malloc申请空间，需要再最后释放空间：free(nums);
• 2.malloc函数需要引用头文件#include<stdlib.h>
• 3.防止下标越界我们尽量用减法计算中间值，避免采用加法（right+left）/2的形式
• while的判定条件 left<= right;

习题：

有一个有序表 1，5 8 11 19  22 31 35 40 45 48 49 50当用二分法查找48的时候应该查找几次

第一次 mid=6 nums[mid]=31<48,left=mid+1=7;right=12;

第二次mid=10,nums[mid]=48 =48,成功找到