专栏首页陶士涵的菜地[javaSE] 数组(查找-二分查找)

[javaSE] 数组(查找-二分查找)

前提数组必须是有序的

定义最小,最大,中间的角标索引

        int min,max,mid;
        min=0;
        max=arr.length-1;
        mid=(min+max)/2;

上面的索引需要变化,使用循环,条件:当中间值不等于目标值时

        int min,max,mid;
        min=0;
        max=arr.length-1;
        mid=(min+max)/2;
        while(arr[mid]!=key){
            if(key<arr[mid]){
                
            }else if(arr[mid]<key){
                
            }
        }

当中间值大于目标值时,最大角标移动到中间角标-1位置

当中间值小于目标值时,最小角标移动到中间角标+1位置

中间角标继续二分

        int min,max,mid;
        min=0;
        max=arr.length-1;
        mid=(min+max)/2;
        while(arr[mid]!=key){
            if(key<arr[mid]){
                max=mid-1;
            }else if(arr[mid]<key){
                min=mid+1;
            }
            mid=(min+max)/2;
        }
        return mid;

此时的代码有问题,当找不到目标时,会陷入死循环,加一个判断

如果一直找不到,最小角标和最大角标会错位

        int min,max,mid;
        min=0;
        max=arr.length-1;
        mid=(min+max)/2;
        while(arr[mid]!=key){
            if(key<arr[mid]){
                max=mid-1;
            }else if(arr[mid]<key){
                min=mid+1;
            }
            if(min>max) return -1;
            mid=(min+max)/2;
        }
        return mid;

java版:

public class ArrayDemo {

    /**
     * @param args
     */
    public static void main(String[] args) {
        int[] arr=new int[]{1,4,6,7,8,9};
        System.out.println("索引:"+keySearch(arr,7));//索引:3
        System.out.println("索引:"+helfSearch(arr,7));//索引:3
    }
    /**
     * 二分查找
     * @param arr
     * @param key
     * @return
     */
    public static int helfSearch(int[] arr,int key){
        int min,max,mid;
        min=0;
        max=arr.length-1;
        mid=(min+max)/2;
        while(arr[mid]!=key){
            if(key<arr[mid]){
                max=mid-1;
            }else if(arr[mid]<key){
                min=mid+1;
            }
            if(min>max) return -1;
            mid=(min+max)/2;
        }
        return mid;
    }
    /**
     * 获取该值在数组中第一次出现的位置
     * @param arr
     * @param num
     * @return
     */
    public static int keySearch(int[] arr,int num){
        for(int i=0;i<arr.length;i++){
            if(arr[i]==num){
                return i;
            }
        }
        return -1;
    }
}

PHP版:

<?php
class ArrayDemo{
    public static function main(){
        $arr=array(1,4,6,7,8,9);
        echo "索引:".ArrayDemo::keySearch($arr,7);//索引:3
        echo "索引:".ArrayDemo::helfSearch($arr,7);//索引:3
    }
    /**
     * 二分查找
     * @param arr
     * @param key
     * @return
     */
    public static function helfSearch($arr,$key){
        $min=0;
        $max=count($arr)-1;
        $mid=ceil(($min+$max)/2);
        while($arr[$mid]!=$key){
            if($key<$arr[$mid]){
                $max=$mid-1;
            }else if($arr[$mid]<$key){
                $min=$mid+1;
            }
            $mid=ceil(($min+$max)/2);
            if($min>$max) return -1;
        }
        return $mid;
    }
    /**
     * 获取该值在数组中第一次出现的位置
     * @param arr
     * @param num
     * @return
     */
    public static function keySearch($arr,$key){
        for($i=0;$i<count($arr);$i++){
            if($arr[$i]==$key){
                return $i;
            }
        }
        return -1;
    }
}

ArrayDemo::main();

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • [Go] Golang练习项目-GO语言实现选择排序

    陶士涵
  • [Go] Golang练习项目-GO实现冒泡排序以及优化算法

    变量lastSwapIndex ,记录最后一次发生交换的位置,后续元素不再进行比较

    陶士涵
  • [PHP] 算法-把数组排成最小的数的PHP实现

    陶士涵
  • 排序之归并排序

      “归并”一词的中文含义就是合并、并入的意思,而在数据结构中的定义是将两个或两个以上的有序表组合成一个新的有序表。既然是归并、并入,那么必然就有子序列了,子序...

  • 腾讯参与下一代视频编解码国际标准制定,预期视频压缩率提升50%

    腾讯音视频实验室
  • 数据分析-NumPy入门使用

    今天我们学习python数据分析中一个很有用的模块NumPy,NumPy是使用Python进行科学计算的基础包。它包含其他内容:

    亚乐记
  • 【LeetCode题解】1186.删除一次得到子数组最大和

    https://leetcode-cn.com/problems/maximum-subarray-sum-with-one-deletion/

    lucifer210
  • python 数据分析超简单入门 : 项目实践篇

    适用于数据分析小白们, up 主也是小白一枚,项目来源于 up 主自学 udacity 中的一个项目实践,up 主自身能力不足,因此文章很浅显, 期待和大神们一...

    刘妍
  • 干货 | python数据分析超简单入门 -- 项目实践篇

    ? ? | 导语 适用于数据分析小白们~ ------ up主也是小白一枚,大家一起交流哈 写在前面的话: PS:文末有上期留言活动开奖结果哦! ①.项目来...

    腾讯NEXT学位
  • 如何扫描二维码显示表格内容

    二维码可以用网址、数字、字母、汉字等表示, 通过扫描二维码,来表示一些特定的信息。最近有朋友咨询,扫描二维码,内容是用表格呈现出来的,该如何制作?如下图:

    用户5746110

扫码关注云+社区

领取腾讯云代金券