赞
踩
二分查找算法是利用数组的二段性进行求解的算法。只要有二段性的数组,都能使用该方法进行求解。
目录>>
2. 34.在排序数组中查找元素的第一个和最后一个位置 searchRange
5. 852.山脉数组的峰顶索引 peakIndexInMountainArray
二分查找算法是利用数组的二段性进行求解的算法。只要有二段性的数组,都能使用该方法进行求解。
找出数组的二段性,运用二分查找进行求解。
朴素二分查找。
- class Solution {
- public int search(int[] nums, int target) {
- int left = 0;
- int right = nums.length - 1; //右端点
- // int mid = (left + right)/2; 容易溢出
- while (left <= right){
- int mid = left + (right - left) / 2; //先求区间的一半,防溢出
- // int mid = left + (right - left) / 3; //区间的三分之一
- if (nums[mid] < target) left = mid+1;
- else if (nums[mid] > target) right = mid-1;
- else return mid;
- }
- return -1;
- }
- }
- class Solution {
- public int[] searchRange(int[] nums, int target) {
- // 处理边界
- int[] ret = new int[2];
- ret[0] = ret[1] = -1;
- if (nums.length == 0) return ret;
-
- // 1,二分左端点
- int left = 0;
- int right = nums.length - 1;
- while (left<right){
- int mid = left + (right - left) / 2;
- if (nums[mid] < target) left = mid +1;
- else right = mid;
- }
- // 判断是否有结果
- if (nums[left] != target) return ret;
- else ret[0] = right;
-
- // 2,二分右端点
- left = 0;
- right = nums.length-1;
- while (left<right){
- int mid = left + (right - left + 1) / 2;
- if (nums[mid] <= target) left = mid;
- else right = mid -1;
- }
- ret[1] = left;
- return ret;
- }
- }
- class Solution {
- public int searchInsert(int[] nums, int target) {
- int left = 0, right = nums.length - 1;
- while (left < right){
- int mid = left + (right - left) / 2;
- if (nums[mid] < target) left = mid+1;
- else right = mid;
- }
- //target比最小的数小,放最左边
- if (nums[left] < target) return left + 1;
- return left;
- }
- }
- class Solution {
- public int mySqrt(int x) {
- if(x < 1) return 0;
- long left = 1, right = x;
- while(left < right)
- {
- long mid = left + (right - left + 1) / 2;
- if(mid * mid <= x) left = mid;
- else right = mid - 1;
- }
- return (int)left;
- }
- }
- class Solution {
- public int peakIndexInMountainArray(int[] arr) {
- int left = 1, right = arr.length - 2;
- while(left < right){
- int mid = left + (right - left + 1) / 2;
- if(arr[mid] > arr[mid - 1]) left = mid;
- else right = mid - 1;
- }
- return left;
- }
- }
- class Solution {
- public int findPeakElement(int[] nums) {
- int left = 0;
- int right = nums.length - 1;
- while (left < right){
- int mid = left + (right - left) / 2;
- if (nums[mid] < nums[mid+1]) left = mid + 1;
- else right = mid;
- }
- return left;
- }
- }
- class Solution {
- public int findMin(int[] nums) {
- int left = 0, right = nums.length - 1;
- int x = nums[right]; // 标记⼀下最后⼀个位置的值
- while(left < right){
- int mid = left + (right - left) / 2;
- if(nums[mid] > x) left = mid + 1;
- else right = mid;
- }
- return nums[left];
- }
- }
一题多解,需要发散思维。
运用 哈希表,直接遍历,异或运算,高斯求和 都能求解出结果,时间复杂度都是O(n)。
但是运用 二分查找 来求解,时间复杂度就是O(logN)。
- int left = 0;
- int right = records.length - 1;
- while (left < right){
- int mid = left + (right - left) / 2;
- if (records[mid] == mid) left = mid +1;
- else right = mid;
- }
- // 细节eg,数组0,1,2,3,缺少4
- return records[left] == left ? left + 1 : left;
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。