【算法学习】二分专场-别说你不会二分啦

二分法

在一个有序数组中,找某个数是否存在

写法1:while判断条件为 left <= right

//在有序数组中找某一个值是否存在
//二分法  left <= right
// 找某一个值是否存在
bool BinarySearch(int* a, int n,int k)
{
	int left = 0;
	int right = n - 1;
	while (left <= right)
	{
      int mid = left + (right - left) / 2;
	    //int mid = (left + right) >> 1;
		int mid = (left + right) / 2;
		if (a[mid] < k)
		{
			left = mid + 1;
		}
		else if (a[mid] > k)
		{
			right = mid - 1;
		}
		else
		{
			return true;
		}
	}
	return false;
}
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

---

写法2：while判断条件为 left < right

最后如果跳出循环了,则需要特判一下 left的值是否是k

//二分法 left < right
bool BinarySearch(int* a, int n,int k)
{
	int left = 0;
	int right = n - 1;
	//L和R至少有两个数才进入循环
	while (left < right)
	{
		int mid = (left + right) >> 1;
		if (a[mid] > k)
		{
			right = mid - 1;
		}
		else if (a[mid] < k)
		{
			left = mid + 1;
		}
		else
		{
			return true;
		}
	}
	//left == true跳出来时：还要判断此时的值是否是k
	return k == a[left];
}
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

---

在一个有序数组中,找>=某个数最左侧的位置

因为找的是>=value最左边的位置,所以二分时,去左边找才更改index的下标

• 先看中间位置的值是否>=value 如果是的话,就去左边找 right = mid -1
• mid位置的值虽然>=value,但是找的是>=value的最左边的位置,数组有序,所以还要继续往mid左边寻找
• 如果中间位置的值< value ，就要去右边找 left = mid + 1
• 中间位置的值=value的数,要去右边找
• 由上述可以得知,只有在去左边找的时候,才更新index的下标为此时的mid位置

//在有序数组中找满足>=value最左边的位置
int BinarySearchLeft(int* a, int n, int value)
{
	int left = 0;
	int right = n - 1;
	int index = -1;//满足的下标
	//死循环找
	while (left <= right)
	{
		int mid = left + (right - left) / 2;
		if (a[mid] >= value)
		{
			//记录当前位置
			index = mid;
			//此时mid往右都是>=value的，要找>=value位置->去左边找
			//去左边找 满足>=value最左边的位置
			right = mid - 1;
		}
		else  //a[mid] < value
		{
			//此时mid往左都是=value位置->去右边找
			//去右边找 满足>=value最左边的位置
			left = mid + 1;
		}
	}
	return index;
}
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

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

因为找的是<=value最右边的位置,所以二分时,去右边找才更改index的下标

• 先看中间位置的值是否<=value 如果是的话,就去右边找 left = mid+1,
  • mid位置的值虽然<=value,但是找的是<=value的最右边的位置,数组有序,所以还要继续往mid右边寻找
• 如果中间位置的值> value ，就要去左边找 right = mid -1
  • 中间位置的值>value,数组有序 ,说明右边都不可能找到<=value的数,要去左边找
• 由上述可以得知,只有在去右边找的时候,才更新index的下标为此时的mid位置

//在有序数组中找满足<=value最右边的位置
int BinarySearchRight(int* a, int n, int value)
{
	int left = 0;
	int right = n - 1;
	int index = -1;//用于记录位置
	while (left <= right)
	{
		int mid = (left + right) >> 2;
		if (a[mid] <= value)
		{
			//记录当前的位置
			index = mid;
			//此时mid往左都是<=value的,要找<=value最右边位置->去右边找
			//去右边找满足<=value最右边的位置
			left = mid + 1;
		}
		else //a[mid] > value
		{
			//此时mid往右都是>=value的,要找<=value最右边位置->要去左边找
			//去左边找满足<=value最右边的位置
			right = mid - 1;
		}
	} 
	return index;
}
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

---

局部最小值问题

定义何为局部最小值：
arr[0] < arr[1]，0位置是局部最小；
arr[N-1] < arr[N-2]，N-1位置是局部最小；
arr[i-1] > arr[i] < arr[i+1]，i位置是局部最小；
给定一个数组arr，已知任何两个相邻的数都不相等，找到随便一个局部最小位置返回

无序数组，值可能为正 负 0，任意两个相邻的数不相等,返回任意一个局部最小位置

• 局部最小值：比左边小 && 比右边小
• 特殊位置：0位置和n-1位置
  • 0位置:arr长度为1时，arr[0]是局部最小或者 a[0] < a[1],0位置就是局部最小值位置
  • n-1位置：只要小于n-2位置就是局部最小
• i位置：比i-1位置小 && 比i+1位置小 就是局部最小

---

思路:

先判断0位置和n-1位置是不是局部最小值位置

如果不符合，则0-1是下降的趋势，n-2 到n-1是上升的趋势。

由于任意两个相邻的数不相等且无序，所以中间肯定存在局部最小 ,在[1,n-2]区域上进行二分查找

---

先找中点位置 如果mid -1 > mid && mid+1 > mid 说明mid就是局部最小值位置,直接返回mid位置

否则：mid -1 > mid || mid+1 > mid，两个必成立一个。 ( 结论 )

mid比哪侧小，就在那一侧二分

//无序数组中局部最小值问题 
int getLessIndex(int* a, int n)
{
	//数组为空 或者 数组长度为0
	if (a == NULL || n == 0)
	{
		return -1; //无局部最小值
	}
	//先判断0位置是不是局部最小值位置
	if (n == 1|| a[0]<a[1])
	{
		return 0;
	}
	//判断n-1位置是不是局部最小值位置
	if (a[n - 1] < a[n - 2])
	{
		return n - 1;
	}
	//在[1,n-2]区间上找局部最小
	//先找中间看是不是,mid比哪侧小,就在哪测二分
	//如果mid比两侧都大,任意一侧二分
	int left = 1;
	int right = n - 2;
	while (left <= right)
	{
		int mid = (left + right) / 2;
		if (a[mid] > a[mid + 1])
		{
			//去小的一侧(右边)二分
			left = mid + 1;
		}
		else if (a[mid] > a[mid-1])
		{
			//去小的一侧二分(左侧)
			right = mid - 1;
		}
		else  // a[mid] < a[mid+1] && a[mid] < a[mid-1]
		{
			return mid;  //如果是打印值的时候,打印完要break,否则可能导致死循环
		}
	}
	// left > 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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

---