都以左闭右闭的方式，即
规定：边界arr[0]<arr[1]，arr[0]即为局部最小，arr[n-1]<arr[n-2]，则arr[n-1]局部最小，中间的数arr[i-1]<arr[i]<arr[i+1]，则arr[i]为局部最小。
问题：一个无序数组，查找局部最小，O(logn)复杂度
若边界都不是局部最小，则中间必有局部最小，取中间位置，若m-1<m则0~m必有局部最小，一直二分下去就能找到。
int l = 0, r = nums.length - 1;
while (l <= r)
int binarySearch(int[] nums, int target) {
// 设置左右边界
int l = 0, r = nums.length - 1;
while (l <= r) {
int mid = l + (r - l) / 2; // 等同于mid=(l+r)/2,这种写法是为了防止数组越界,也可以写为(l+r) >>> 1
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
l = mid + 1;
} else if {
r = mid - 1;
}
}
// 最后判断: l>r 即数组不存在
return -1;
}
int left_bound(int[] nums, int target) {
int l = 0, r = nums.length - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (nums[mid] < target) {
l = mid + 1;
} else if (nums[mid] > target) {
r = mid - 1;
} else if (nums[mid] == target) {
// 收缩右侧边界
r = mid - 1;
}
}
// 判断 target 是否存在于 nums 中
// 如果越界，target 肯定不存在，返回 -1
if (l < 0 || l >= nums.length) {
return -1;
}
// 判断一下 nums[l] 是不是 target
return nums[l] == target ? l : -1;
}
int right_bound(int[] nums, int target) {
int l = 0, r = nums.length - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (nums[mid] == target) {
l = mid + 1;
} else if (nums[mid] < target) {
l = mid + 1;
} else if (nums[mid] > target) {
r = mid - 1;
}
}
if (r < 0 || r >= nums.length) {
return -1;
}
return nums[r] == target ? r : -1;
}
public class binary {
int binarySearch(int[] nums, int target) {
// 设置左右边界
int l = 0, r = nums.length - 1;
while (l <= r) {
int mid = l + (r - l) / 2; // 等同于mid=(l+r)/2,这种写法是为了防止数组越界,也可以写为(l+r) >>> 1
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
l = mid + 1;
} else if {
r = mid - 1;
}
}
// 最后判断: l>r 即数组不存在
return -1;
}
public static int left_bound(int[] nums, int target) {
int l = 0, r = nums.length - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (nums[mid] == target) {
// 收缩右侧边界
r = mid - 1;
} else if (nums[mid] > target) {
r = mid - 1;
} else if (nums[mid] < target) {
l = mid + 1;
}
}
// 判断 target 是否存在于 nums 中
// 如果越界，target 肯定不存在，返回 -1
if (l < 0 || l >= nums.length) {
return -1;
}
// 判断一下 nums[l] 是不是 target
return nums[l] == target ? l : -1;
}
public static int right_bound(int[] nums, int target) {
int l = 0, r = nums.length - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (nums[mid] == target) {
l = mid + 1;
} else if (nums[mid] < target) {
l = mid + 1;
} else if (nums[mid] > target) {
r = mid - 1;
}
}
if (r < 0 || r >= nums.length) {
return -1;
}
return nums[r] == target ? r : -1;
}
public static void main(String[] args) throws Exception {
int[] arr = {1, 2, 2, 2, 2, 2, 7, 8};
//int index = binarySearch(arr, 2);
//int index = left_bound(arr, 2);
int index = right_bound(arr, 2);
System.out.println(index);
}
}