二分查找

[编程题]二分查找

热度指数：1085 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个递增排序的数组，查找某个数字是否在数组中，如果在数组中，则返回该数字在数组中第一次出现的位置（从0开始）；如果不在数组中，返回-1 。

不需要考虑给定的数组不是递增的情况。

务必使用二分查找的方式。

示例1

输入

[1,2,3],3

输出

示例2

输入

[1,2,3],4

输出

-1

备注:

注意只能用二分查找，其他方式零分。

算法知识视频讲解

Java

牛客617355593号

import java.util.*;

public class Solution {
/**
*
* @param arr int整型一维数组
* @param a int整型要查找的数字
* @return int整型
*/
public int binarySearch (int[] arr, int a) {
// write code here
int left = 0,right = arr.length-1;
while(left<= right){
int middle = left +(right-left)/2;
if(arr[middle]<a){
left = middle+1;
}
if(arr[middle]>=a){
right = middle-1;
}
}
if(left == arr.length){
return -1;
}
return left ;
}
}

发表于 2021-11-09 12:00:27 回复(0)

Java

天使踩麻木

import java.util.*;


public class Solution {
    /**
     * 
     * @param arr int整型一维数组 
     * @param a int整型 要查找的数字
     * @return int整型
     */
    public int binarySearch (int[] arr, int num) {
        // write code here
        if(arr.length<=0){
            return -1;
        }
        
        int left =0;    // 左脚标
        int right =arr.length-1;    // 右脚标
        
        // 一直到left== right 时跳出循环
        while(left<right){
            int mid = (left+right)>>1;
            if(arr[mid]<num){
                left=mid+1;
            }else{
                right=mid;
            }
        }
        return arr[left]==num ? left:-1;
    }
}

编辑于 2021-07-20 18:21:38 回复(0)