Binary search with Java, system if number not present?

ButterkeksLp1ByButterkeksLp1

Good morning,

The following:

I have an array with 25,000 fields, in which square numbers are stored in ascending order. The program currently queries the user for the number it's looking for and then systematically searches the array using approximation. I just have absolutely no idea how to implement it so that it detects when the number isn't there. My idea was to divide the variable from the last attempt by the variable from the current attempt, and if the result is 0, it should output that the number isn't there. Unfortunately, this sometimes causes it to display that the number isn't there, even though it is, whenever it searches a field next to the number being searched for. Here's the relevant part of the code:

 int resultIndex; int bereich = 12500; int alg = 6250; int bereich2 = 0; while(true) { if(quadratZahlen[bereich] < zahl) { bereich = bereich + alg; alg = alg / 2; } else if(quadratZahlen[bereich] == zahl) { resultIndex = bereich; break; } else if(quadratZahlen[bereich] > zahl) { bereich = bereich / 2; alg = bereich / 2; } int test = bereich - bereich2; if (test == 0) { resultIndex = -1; break; } bereich2 = bereich; }

range2 is the variable of the last search

area of ​​the current search

alg is only used to recalculate the range if the number was not found

resultIndex shows the position of the found number

(1 votes)
Loading...

Similar Posts

[C++] How to change the color of a FlowLayoutPanel slider?

ByF7ebwiskro2

I built a small GUI using C++ and the CLI "support/building tool." However, the "slider bar"—I have no idea what it's called—is light gray, not dark. Is there a way to change this bar color? My GUI is rather dark, so the "sliding bar" is extremely noticeable. Does anyone have any ideas? Best regards 🙂

How many kilometers does a normal airliner need to travel to reach its target altitude?

ByAnmaroni

Let's assume a normal, standard passenger aircraft. Please also assume the target altitude at the standard altitude. How long would the ground-air distance be until it reached its target altitude? I'm interested, as there's an airport 21 km away from me as the crow flies. I wonder if the planes taking off from there have…

Can I connect a USB-C docking station to a PC with a USB-A adapter?

ByCorvocorvo

I would like to connect two monitors and other hardware (headset, mouse, keyboard, etc.) via a docking station. But my PC doesn't have a USB-C port. Can I simply convert the USB-C signal to a USB-A port using an adapter? For example, with the DELOCK 65698 USB 3.1 Converter, A male to C female (Google…

Subscribe
Notify of
5 Answers
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
KarlRanseierIII
KarlRanseierIII
1 year ago

If you want to make it much easier, then you take two indices, L and R and, depending on, R is set to the middle between L and R or vice versa.

Once L=R you can finish the loop, which corresponds to a “not found”.

P.S.: What is the meaning of looking in a list of square numbers?

0
ButterkeksLp1
Author
ButterkeksLp1
1 year ago
Reply to  KarlRanseierIII

Doesn’t make sense, it’s just an exercise at university. Thank you very much

0
regex9
regex9
1 year ago

Your loop needs a dynamic condition in your head. Since you keep halving the search area in a binary search, you have at some point (case) only a quantity of 1. If this is the case (and there is no find), the loop must be terminated. The variable Result index you can initialize with -1. Only at Fund is their value overwritten.

Addendum:

An iterative search could look like this:

int index = -1;
int start = 0;
int end = haystack.length - 1;

while (start <= end) {
  int pivot = start + (end - start) / 2;

  if (haystack[pivot] == needle) {
    index = pivot;
    break;
  }

  if (haystack[pivot] < needle) {
    start = pivot + 1;
  }
  else {
    end = pivot - 1;
  }
}

I use two variables (start, end), which represent the boundaries of the area to be searched. With each run, they are recalculated and, on this basis, an average / anchor point (ivot) is determined.

3
verreisterNutzer
verreisterNutzer
1 year ago

You don't have to unlock the algorithm yourself; Implementations of binary search can be found on the Internet, eg http://www.geeksforgeeks.org .

 import java.util.List; import java.util.ArrayList; public class Main { public static void main(String args[]) { // Liste der Quadratzahlen generieren int[] quadratZahlen = new int[25000]; for(int i = 0; i < 25000; i++) { quadratZahlen[i] = (int) Math.pow(i, 2); } // Wurzel finden mittels binärer Suche int zahl = 15129; int wurzel = binaereSuche(quadratZahlen, zahl); if(wurzel == -1) { System.out.println(zahl + " ist keine Quadratzahl."); } else { System.out.println("Die Wurzel von " + zahl + " ist " + wurzel + "."); } } // Implementierung des Algorithmus nach https://www.geeksforgeeks.org/binary-search/ // gibt Index von x in arr[] (= entspricht der Wurzel) zurück, falls vorhanden public static int binaereSuche(int arr[], int x) { int l = 0, r = arr.length - 1; while(l <= r) { int m = l + (r - l) / 2; // prüfen, ob x in der Mitte liegt if(arr[m] == x) { return m; } if(arr[m] < x) { // wenn x größer ist, linke Hälfte ignorieren l = m + 1; } else { // wenn x kleiner ist, rechte Hälfte ignorieren r = m - 1; } } // x ist nicht in arr[] vorhanden, dh keine Quadratzahl return -1; } }

To this end, an explanation video on the functioning of the binary search:

https://www.youtube.com/watch?v=XJUgCSejezQ

1
ButterkeksLp1
Author
ButterkeksLp1
1 year ago
Reply to  verreisterNutzer

Thank you.

0