二分查找——面试必刷TOP101

二分查找

BM17 二分查找-I

import java.util.*;

public class Solution {

    public int search (int[] nums, int target) {
        int i=0,j=nums.length-1;
        while(i<=j){
            int m=(i+j)/2;
            if(nums[m]==target) return m;
            else if(nums[m]>target) j=m-1;
            else i=m+1;
        }
        return -1;
    }
}

BM19 寻找峰值

import java.util.*;

public class Solution {

    public int findPeakElement (int[] nums) {
        int i=0,j=nums.length-1;
        while(i
            int m=(i+j)/2;
            if(nums[m]>nums[m+1]) j=m;
            else i=m+1;
        }
        return j;
    }
}

BM21 旋转数组的最小数字

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        int i=0,j=array.length-1;
        while(i
            int m=i+(j-i)/2;
            if(array[m]>array[j]) i=m+1;
            else if(array[m] 
34.在排序数组中查找元素的第一个和最后一个位置
 
class Solution {
    public int[] searchRange(int[] nums, int target) {
        if(nums.length == 0) return new int[]{-1,-1};    
        int l = 0, r = nums.length - 1; 
        while( l < r){//查找元素的左位置
            int m = (l + r)/2;
            if(nums[m] >= target) r = m;
            else l = m + 1;
        }
        if( nums[r] != target) return new int[]{-1,-1}; //查找失败
        int L = r;
        l = 0; r = nums.length - 1;    
        while( l < r){//查找元素的右位置
            int m = (l + r + 1)/2;//+1是为了防止死循环
            if(nums[m] <= target ) l = m;
            else  r = m-1;
        }
        return new int[]{L,r};
    }
}
 
BM18 二维数组中的查找
 
public class Solution {
    public boolean Find(int target, int [][] arr) {
        int i=arr.length-1,j=0;
        while(i>=0 &&j
            if(arr[i][j]==target) return true;
            else if(arr[i][j]>target) i--;
            else j++;
        }
        return false;
    }
}