二分查找

[编程题]二分查找

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

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

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

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

示例1

输入

[1,2,3],3

输出

示例2

输入

[1,2,3],4

输出

-1

备注:

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

算法知识视频讲解

不延毕跑半马的王师傅

class Solution:
def binarySearch(self , arr , a ):
left = 0
right = len(arr)
#在list[left...right]里查找target，注意是左闭右闭
while left < right:
mid = (right + left)//2 #取中间元素索引
if arr[mid] == a:
return mid
elif a > arr[mid]:
left = mid+1#到list[mid + 1 ...right]里查找
else: #target < list[mid]
right = mid #到list[left ...mid - 1]里查找
return -1

发表于 2022-08-09 16:29:07 回复(0)

wonderson

public int binarySearch (int[] arr, int a) { int lo = 0, hi = arr.length - 1; while (lo < hi) { int m = (hi - lo) / 2 + lo; if (arr[m] < a) { lo = m + 1; } else { hi = m; } } return arr[lo] == a ? lo : -1; }

发表于 2022-03-09 14:20:04 回复(0)

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)

C/C++

想拿A追梦人在写日记

 int binarySearch(int* arr, int arrLen, int a) {
        // write code here
        int left = 0;
        int right = arrLen-1;
        int mid = 0;
        while(left<=right)
        {
            mid = (left+right)/2;
            if(arr[mid]==a)
            {
                if(arr[mid-1]!=a)
                    return mid;
                else
                    return mid-1;
            }        
            else if(arr[mid]>a)
                right = mid - 1;
            else
                left = mid + 1;
        }  
        return -1;
    }

发表于 2021-09-07 20:23:17 回复(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)

FrankKong

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 l = 0, r = arr.length - 1;
        while(l < r){
            int mid = (l + r) >> 1;
            if(arr[mid] >= a) r = mid;
            else l = mid + 1;
        }
        return arr[l] == a ? l : -1;
    }
}

发表于 2021-02-24 09:09:34 回复(0)