学习数据结构笔记(15) --- [二分查找算法(非递归)]

力扣这道题其实就是二分查找的基础考察题目
704. 二分查找
写完可以多找几道二分查找的题试试

二分查找的前提是这个数组是一个有序的数组;
我们这里将规定为升序数组;

定义中间数值的索引; 若要找的目标值就是这个中间值,直接返回即可;
若找的目标值大于中间数,则将查询范围缩小到中间数的右边;
若找的目标值小于中间数,则将查询范围缩小到中间数的左边;

    public static int binarySearch(int[] array, int target){
        //定义左右指针,
        int left = 0;
        int right = array.length-1;
        
        while (left<=right){
            //中点;
            int middle = left+( right -left)/2;
            //若找到目标数返回;若大于目标数,在左边查找; 小于目标数,在右边查找;
            if(array[middle] == target) 
                return middle;
            if(array[middle] > target)
                right = middle - 1;
            if (array[middle] < target)
                left = middle + 1;
        }
        //若没找到,返回-1;
        return -1;
    }

还可以用这个模板进行查找

class Solution {
    public int search(int[] nums, int target) {
       //先临时统计,查找是否有目标值;
       int temp = 0 ;
       for(int i =0;i 
力扣34题:在排序数组中查找元素的第一个出现位置,以及最后一次出现位置;若不存在则返回-1;将两个结果封装到数组中;
 34. 在排序数组中查找元素的第一个和最后一个位置
 
题目描述:
 
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
进阶：
你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
 
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：
输入：nums = [], target = 0
输出：[-1,-1]

提示：
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109
 
使用二分查找模板;
 找第一个目标元素时,找到第一个小于目标值的位置即可;返回的是最后的右指针位置;注意,有可能找不到指定的元素;若此时的位置不是目标元素;就说明不存在,返回-1;
 找第二个目标元素时,找到第一个大于目标值的位置即可,但会的是最后的左指针位置;注意,这时也有可能找不到指定元素,若此时的位置不是目标元素,说明不存在,返回-1;
 
class Solution {
    public int[] searchRange(int[] nums, int target) {
       //若数组长度为0,或者当前目标元素并不存在,则返回数组[-1,-1]
       if(nums.length==0 ||nums[0]>target||nums[nums.length-1] 
封装到方法中
 
public class BSDemo {
    public static void main(String[] args) {

        int[] arr = {1,3,3,3,3,6,9,12,53};
        int index = getFirst(arr, 3);
        System.out.println("第一次出现的位置-->"+index);
        //找到第一个出现的元素;
        int last = getLast(arr, 3);
        System.out.println("最后一次出现的位置-->"+last);
    }

    
    public static int getFirst(int[] arr, int target) {
        //若不符合,直接返回;
        if (arr.length == 0 || arr[0] > target || arr[1] < target)
            return -1;
        //定义左右指针;中轴索引;
        int left = -1;
        int right = arr.length;
        int middle;
        while (left + 1 != right) {
            //计算中轴索引;
            middle = left + (right - left) / 2;
            if (arr[middle] < target) {
                left = middle;
            } else {
                right = middle;
            }
        }
        return (arr[right] == target) ? right : -1;
    }

    
    public static int getLast(int[] arr,int target){
        //定义左右指针;中轴索引;
        int left = -1;
        int right = arr.length;
        int middle;
        while (left + 1 != right) {
            //计算中轴索引;
            middle = left + (right - left) / 2;
            if (arr[middle] <= target) {
                left = middle;
            } else {
                right = middle;
            }
        }
        return (arr[left] == target) ? left : -1;
    }
}