二分查找-leetcode
/**
*
* 278. First Bad Version
*
* You are a product manager and currently leading a team to develop a new
* product. Unfortunately, the latest version of your product fails the quality
* check. Since each version is developed based on the previous version, all the
* versions after a bad version are also bad.
*
* Suppose you have n versions [1, 2, ..., n] and you want to find out the first
* bad one, which causes all the following ones to be bad.
*
* You are given an API bool isBadVersion(version) which will return whether
* version is bad. Implement a function to find the first bad version. You
* should minimize the number of calls to the API.
*
* note: The isBadVersion API is defined in the parent class VersionControl.
* boolean isBadVersion(int version);
*
*/
public class Lc278 {
/*
* 本题利用二分查找，不同于普通的二分查找，本题是利用二分发找到最先出现的bad code，所以利用折半找到对应位置。
*
* 需要注意的是常规的二分法是利用mid = (left+right)/2;如果left =
* Integer.maxValue,right=Inter.maxValue,就会超过啦 可以用 left + （right-left） 就可以避免以上情况
*/
public static int firstBadVersion(int n) {
int left = 1;
int right = n;
while (right > left) {
int mid = left + (right - left) / 2;
if (isBadVersion(mid)) {
right = mid;
} else {
left = left + 1;
}
}
return left;
}
public static boolean isBadVersion(int version) {
return false;
}
public static void main(String[] args) {
System.out.println(firstBadVersion(5));
}
}
/**
* Given a sorted array and a target value, return the index if the target is
* found. If not, return the index where it would be if it were inserted in
* order.
*
* You may assume no duplicates in the array.
*
*
*/
public class Lc35 {
/**
*标准的二分查找题目
*
*
*/
public static int searchInsert(int[] nums, int target) {
if (nums.length == 0) {
return 0;
}
int left = 0;
int right = nums.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] > target) {
right = mid;
} else if (nums[mid] < target) {
left = mid + 1;
}
}
return ++right;
}
public static void main(String[] args) {
int[] nums = { 1, 3 };
int target = 2;
System.out.println(searchInsert(nums, target));
}
}
import java.util.Arrays;
/**
*
* 33. Search in Rotated Sorted Array
*
* Suppose an array sorted in ascending order is rotated at some pivot unknown
* to you beforehand.
*
* (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
*
* You are given a target value to search. If found in the array return its
* index, otherwise return -1.
*
* You may assume no duplicate exists in the array.
*
* Your algorithm's runtime complexity must be in the order of O(log n).
*
*/
public class Lc33 {
/**
* 数组之间相互指向是地址指向，值改变双方都是改变
*
*/
public static int search(int[] nums, int target) {
if (nums.length == 0) {
return -1;
}
// 复制到新的空间
int temp[] = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
temp[i] = nums[i];
}
// 排序
Arrays.sort(temp);
int left = 0;
int right = nums.length;
// 记录目标数据在排序后数组中的位置
int position = Integer.MAX_VALUE;
while (left < right) {
int mid = left + (right - left) / 2;
if (target == temp[mid]) {
position = mid;
break;
} else if (temp[mid] > target) {
right = mid;
} else if (temp[mid] < target) {
left = left + 1;
}
}
// 数组中无该数据
if (position == Integer.MAX_VALUE) {
return -1;
}
// 找到目标数据在数组中的位置，找到对应值在原数组的位置
for (int i = 0; i < nums.length; i++) {
if (nums[i] == temp[position]) {
return i;
}
}
return nums.length;
}
public static void main(String[] args) {
int nums[] = { 4, 5, 6, 7, 0, 1, 2 };
int target = 0;
System.out.println(search(nums, target));
}
}
/*
*
* 153. Find Minimum in Rotated Sorted Array
*
*
* Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
Find the minimum element.
You may assume no duplicate exists in the array.
*/
public class Lc153 {
/*
* 首先对比俩端的数字，如果是左边小于右边，则无需比较，整体是升序；
*
* 如果左边大于右边，如果中间位置的值大于左边，则中间值也在一组升序里面，则需让左边的边界为中间值 同理 右边也是
*/
public static int findMin(int[] nums) {
int left = 0;
int right = nums.length;
if (nums[left] < nums[right - 1]) {
return nums[0];
}
while (left < right - 2) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[left]) {
left = mid;
} else if (nums[mid] < nums[left]) {
right = mid;
}
}
return nums[right];
}
public static void main(String[] args) {
int[] nums = { 4, 5, 6, 7, 0, 1, 2 };
System.out.println(findMin(nums));
}
}
/*
* We are playing the Guess Game. The game is as follows:
I pick a number from 1 to n. You have to guess which number I picked.
Every time you guess wrong, I'll tell you whether the number is higher or lower.
You call a pre-defined API guess(int num) which returns 3 possible results (-1, 1, or 0):
*/
public class Lc374 {
/*
* guess(int num)
*/
public static int guessNumber(int n) {
int left = 1;
int right = n;
while (left < right) {
int mid = left + (right - left) / 2;
int res = guess(mid);
if (res == 0) {
return mid;
} else if (res == -1) {
right = mid-1;
} else if (res == 1) {
left = mid+1;
}
}
return n;
}
private static int guess(int num) {
if (num < 2) {
return -1;
}
if (num > 2) {
return 1;
}
return 0;
}
public static void main(String[] args) {
System.out.println(guessNumber(2));
}
}