在一个有重复元素的排序列表中找到第一个出现的整数。

huangapple
go评论119阅读模式
英文:

Find first occurrence of an integer in a sorted list with duplicates

问题

这段代码在数组中正确打印了元素"k"的第一个出现位置，但是我正在处理的问题要求我在数组中根本不存在元素"k"的情况下打印-1。我知道这很简单，但我卡住了，感到很沮丧，有人能帮忙吗？

  1. n = sc.nextInt();
  2. k = sc.nextInt();
  3. int arr[] = new int[n];
  4. for(int i=0; i<n; i++) {
  5.     arr[i] = sc.nextInt();
  6. }
  7. int foundIndex = -1;
  8. for(int i=0; i<n; i++) {
  9.     if(arr[i] == k) {
  10.         foundIndex = i;
  11.         break;
  12.     }
  13. }
  14. System.out.println(foundIndex);
英文:

This code prints the first occurence of element 'k' in the array properly but the question I'm doing wants me to print -1 if the element 'k' is entirely not present in the array. I know its easy but I'm just stuck and its frustatiting any help?

  1. n = sc.nextInt();
  2. k = sc.nextInt();
  3. int arr[] = new int[n];
  4. for(int i=0;i&lt;n;i++) {
  5.     arr[i] = sc.nextInt();
  6. }
  7. for(int i=0;i&lt;n;i++) {
  8.     if(arr[i]==k) {
  9.         System.out.println(i);
  10.         break;
  11.     }
  12. }

答案1

得分: 1

使用Arrays#binarySearch：

  1. int firstIndexOf(int[] sortedArray, int x) {
  2.     int p = Arrays.binarySearch(sortedArray, x);
  3.     if (p < 0) {
  4.         return -1;
  5.     }
  6.     while (p > 0 && sortedArray[p - 1] == x) {
  7.         --p;
  8.     }
  9.     return p;
  10. }

二分查找将搜索范围反复分成两半，确定继续搜索的半边。它会返回找到的位置，或是插入位置的补码(~p)。

英文:

Use Arrays#binarySearch:

  1. int firstIndexOf(int[] sortedArray, int x) {
  2.     int p = Arrays.binarySearch(sortedArray, x);
  3.     if (p &lt; 0) {
  4.         return -1;
  5.     }
  6.     while (p &gt; 0 &amp;&amp; sortedArray
     == x) {
  7.         --p;
  8.     }
  9.     return p;
  10. }

Binary search splits the searched range in half repetively looking in which half to continue. It returns either the found position or the complement (~p) of the insert position.

答案2

得分: 0

你在标题中提出的问题和你在帖子正文中提出的问题是两个不同的问题；然而，如果我们遵循你问题的正文，那与二分搜索毫无关系，引入布尔标志将使你得到你所要求的：

  1. boolean notFound = true;
  3. for(int i=0; i<n; i++) {
  4.     if(arr[i] == k) {
  5.         System.out.println(i);
  6.         notFound = false;
  7.         break;
  8.     }
  9. }
  11. if(notFound) System.out.println("-1");
英文:

What you are asking in the title, and what you are asking in the post body, are two different questions; however, if we will follow your question's body, that has nothing to do with binary search, and introducing boolean flag would get you what you are asking for:

  1. boolean notFound = true;
  3. for(int i=0; i&lt;n; i++) {
  4.     if(arr[i] == k) {
  5.         System.out.println(i);
  6.         notFound = false;
  7.         break;
  8.     }
  9. }
  11. if(notFound) System.out.println(&quot;-1&quot;);

答案3

得分: 0

  1. int findOccurenceOfElemet(int[] a, int k) {
  2.     if(a.length == 0) {
  3.         return -1;
  4.     }
  6.     for(int i = 0; i < a.length; i++) {
  7.         if(a[i] == k) {
  8.             return i;
  9.         }
  10.     }
  11.     
  12.     // 如果未找到元素，返回-1
  13.     return -1;
  14. }
英文: 
  1. int findOccurenceOfElemet(int[] a, int k) {
  2.         if(a.length == 0) {
  3.             return -1;
  4.         }
  6.         for(int i = 0; i &lt; a.length; i++) {
  7.             if(a[i] == k) {
  8.                 return i;
  9.             }
  10.         }
  11.         
  12.         //return -1 if element not found
  13.         return -1;
  14.     }

huangapple
  • 本文由 发表于 2020年10月15日 23:10:17
  • 转载请务必保留本文链接：https://go.coder-hub.com/64374632.html
  • arrays
  • binary-search
  • java
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定