查找数字x是否在有序数组中(无重复)

key

  • 左闭右闭区间
  • left<=right
  • 无重复
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 查找数字x是否在有序数组中,无重复
public static int f1(int[] a, int x) {
	int left = 0;
	int right = a.length - 1;
	int mid = 0;
	// 区间是[0,n-1]
	while (left <= right) {
		mid = (left + right) / 2;
		if (a[mid] == x) {
			return mid;
		} else if (a[mid] > x) {
			// 在区间[left,mid-1]找
			right = mid - 1;
		} else {
			// 在区间[mid+1,right]找
			left = mid + 1;
		}
	}
	// 找不到
	return -1;
}

序列的第一个x的位置L(有重复)

对于出现左闭右开区间，应会出现r=mid或者l=mid，且循环条件是改为left<right
key

  • 有重复
  • 左闭右开区间
  • left < right
  • 出现r=mid或者l=mid
  • 返回left
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//序列的第一个x的位置
public static int f2(int[] a, int x) {
	int left = 0;
	int right = a.length;
	int mid = 0;
	// 区间是[0,n)
	// 分支中出现了l=mid 或者r=mid，循环条件要写成left < right，否则写成left <= right
	//避免出现left=right-1出现死循环
	while (left < right) {
		mid = (left + right) / 2;
		if (a[mid] >= x) {
			// 在区间[left,mid)找
			//因为是左闭右开区间，所以right=mid
			right = mid;
		} else {
			// 在区间[mid+1,right)找
			left = mid + 1;
		}
	}
	//返回左
	return left;
}

序列的第一个大于x的位置R(有重复)

key

  • 有重复
  • 左闭右开区间
  • left < right
  • 出现r=mid或者l=mid
  • 返回left
  • a[mid] > x无等号
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//第一个大于x的位置R
public static int f3(int[] a, int x) {
	int left = 0;
	int right = a.length;
	int mid = 0;
	// 区间是[0,n)
	// 分支中出现了l=mid 或者r=mid，循环条件要写成left < right，否则写成left <= right
	//避免出现left=right-1出现死循环
	while (left < right) {
		mid = (left + right) / 2;
		//第一个大于x的元素，没有等号
		if (a[mid] > x) {
			// 在区间[left,mid)找
			right = mid;
		} else {
			// 在区间[mid+1,right)找
			left = mid + 1;
		}
	}
	// 找不到
	return left;
}

练习

34. Search for a Range