在一个有序数组中,找某个数是否存在

简介: 在一个有序数组中,找某个数是否存在
package com.harrison.Class01;
import java.util.Arrays;
public class Code04_BSExist {
  public static boolean exist(int[] sortedArr,int num) {
    if(sortedArr==null || sortedArr.length==0) {
      return false;
    }
    int l=0;
    int r=sortedArr.length-1;
    int mid=0;
    while(l<r) {
      mid=l+((r-l)>>1);
      if(sortedArr[mid]==num) {
        return true;
      }else if(sortedArr[mid]>num) {
        r=mid-1;
      }else {
        l=mid+1;
      }
    }
    return sortedArr[l]==num;
  }
  public static boolean test(int[] sortedArr,int num) {
    for(int cur:sortedArr) {
      if(cur==num) {
        return true;
      }
    }
    return false;
  }
  public static int[] generateRandomArray(int maxSize,int maxValue) {
    int[] arr=new int[(int)(Math.random()*(maxSize+1))];
    for(int i=0; i<arr.length; i++) {
      arr[i]=(int)(Math.random()*(maxValue+1))-(int)(Math.random()*maxValue);
    }
    return arr;
  }
  public static void main(String[] args) {
    int testTimes=1000000;
    int maxSize=100;
    int maxValue=100;
    boolean succeed=true;
    for(int i=0; i<testTimes; i++) {
      int[] arr=generateRandomArray(maxSize, maxValue);
      Arrays.sort(arr);
      int num=(int)(Math.random()*(maxValue+1))-(int)(Math.random()*maxValue); 
      if(exist(arr, num)!=test(arr, num)) {
        succeed=false;
        break;
      }
    }
    System.out.println(succeed?"Nice":"Fucking fucked");
  }
}


相关文章
【剑指offer】-把数组排成最小的数-33/67
【剑指offer】-把数组排成最小的数-33/67
|
7月前
leetcode-6129:全 0 子数组的数目
leetcode-6129:全 0 子数组的数目
71 0
【Leetcode -605.种花问题 -628.三个数的最大乘积】
【Leetcode -605.种花问题 -628.三个数的最大乘积】
32 0
|
算法 C语言 C++
【二分查找】668. 乘法表中第k小的数
【二分查找】668. 乘法表中第k小的数 在另一篇博客里讲过二分法的模板: 《二分法的模板讲解》
75 0
|
Python
找几个数的最大乘积
找几个数的最大乘积
78 0
|
索引
三个数的最大乘积
三个数的最大乘积
71 0
剑指offer 46. 把数组排成最小的数
剑指offer 46. 把数组排成最小的数
83 0
二分 :数的范围
二分 :数的范围
71 0
【LeetCode 327】区间和的个数
【LeetCode 327】区间和的个数
116 0

热门文章

最新文章