【查找算法】——二分查找

查找算法

二分查找

在 有序序列 区间[left，right]中查找目标值Target。首先找到区间内的中间位置[mid]的值，和目标值作比较。如果大于目标值，则向左查找*（假设为升序序列）；如果小于目标值，则向右查找（假设为升序序列）*

术语

• Target --> 目标值
• left --> 左边界
• right --> 右边界
• mid --> 中间值，可用来确定下一轮是左查找还是右查找

模板

• [left, right]

C语言：

int search(int* nums, int numsSize, int target){
    
    /* left,right 定义 */
    int left = 0;
    int right = numsSize - 1;
    while (left <= right) {
        /* 取区间的中间值，此处不可用(left + right) / 2, 返回值相加溢出 */
        int mid = left + ((right - left) / 2);
        if (nums[mid] > target) {
        	/* 中间值大于目标值，将区间右边界移动到mid-1 */       
            right = mid - 1;
        } else if (nums[mid] < target) {
        	/* 中间值小于目标值，将区间左边界移动到mid+1 */
            left = mid + 1;
        } else {
            /* 找到位置 */
            return mid;
        }
    }

    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

• [left, right)

C语言：

int search(int* nums, int numsSize, int target){
    
    /* left,right 定义 */
    int left = 0;
    int right = numsSize;
    /* right不参与比较，left == right时退出，需要判断边界left */
    while (left < right) {
        /* 取区间的中间值，此处不可用(left + right) / 2, 返回值相加溢出 */
        int mid = left + ((right - left) / 2);
        if (nums[mid] > target) {
        	/* 中间值大于目标值，将区间右边界移动到mid */       
            right = mid;
        } else if (nums[mid] < target) {
        	/* 中间值小于目标值，将区间左边界移动到mid+1 */
            left = mid + 1;
        } else {
            /* 找到位置 */
            return mid;
        }
    }
	
	if ((left != numsSize) || (nums[left] == target)) {
        return left;
	}
 
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

** [278. 第一个错误的版本]**

/* 错误版本相当于[0,0,0,0,0,1,1,1]中查找1第一次出现的位置 */
/* 采用左闭右开，当中间值为1时，将该位置定义为右边界，在[left, right)查找是否还有1 */
/* 直到left == right时，right就是1第一次出现的位置，也就是该题目中firstBadVersion的位置 */
int firstBadVersion(int n) {
    int left = 1;
    int right = n;
    while (left < right) {
        int mid = left + ((right - left) / 2);
        /* isBadVersion提供的接口，true表示是坏版本 */
        if (isBadVersion(mid) == true) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return right;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

• (left, right)

C语言：

int search(int* nums, int numsSize, int target){
    
    /* left,right 定义 */
    int left = 0;
    int right = numsSize;
    /* left和right不参与比较，需要判断边界 */
    while (left + 1 < right) {
        /* 取区间的中间值，此处不可用(left + right) / 2, 返回值相加溢出 */
        int mid = left + ((right - left) / 2);
        if (nums[mid] > target) {
        	/* 中间值大于目标值，将区间右边界移动到mid */       
            right = mid;
        } else if (nums[mid] < target) {
        	/* 中间值小于目标值，将区间左边界移动到mid */
            left = mid;
        } else {
            /* 找到位置 */
            return mid;
        }
    }
	
	if (nums[left] == target) {
        return left;
	} else if (nums[right] == target) {
        return right;
    }
 
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

** [162. 寻找峰值]**

int findPeakElement(int* nums, int numsSize){
    int left = 0;
    int right = numsSize;
    /* 退出循环时left， right相邻，left是峰值 */
    while (left + 1 < right) {
        int mid = left + ((right - left) / 2) ;    
        if (nums[mid - 1] < nums[mid]) {
            /* 处于上坡时移动left */
            left = mid;
        } else if (nums[mid] < nums[mid - 1]) {
            /* 处于下坡时移动right */
            right = mid;
        }
    }

    return left;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17