Binary Search Depiction


Författare/Upphovsman:
AlwaysAngry
Tillskrivning:
Bilden är taggad "Attribution Required" men ingen tillskrivningsinformation lämnades. Attributionsparametern utelämnades troligen när MediaWiki-mallen användes för CC-BY-licenserna. Författare och upphovsmän hittar ett exempel för korrekt användning av mallarna här.
Kreditera:
Eget arbete
Kort länk:
https://sewiki.info/b/b5213
Källa:
Wikimedia Commons
Upplösning:
470 x 200 Pixel (5806 Bytes)
Beskrivning:
This is an example of a binary search steps through time. Source code and output: 
int[] numbersArray = {1,3,4,6,7,8,10,13,14,18,19,21,24,37,40,45,71};
public boolean binarySearchAlgorithm(int targetNumber, int[] numbers)
{
    int lowerLimit = 0;
    int upperLimit = numbers.length - 1;

    while (upperLimit >= lowerLimit)
    {
        int middleNumber = (lowerLimit + upperLimit)/2;

        if (numbers[middleNumber] == targetNumber)
        {
            return true;
        }
        if (numbers[middleNumber] < targetNumber)
        {
            lowerLimit = middleNumber + 1;
        }
        if (numbers[middleNumber] > targetNumber)
        {
            upperLimit = middleNumber - 1;
        }
    }
    return false;
}
System.out.println(binarySearchAlgorithm(7, numbersArray)); //prints "true"

iteration 1

  1. low = 0
  2. high = 16
  3. middle = (0+16)/2 = 16/2 = 8
  4. 7 (target at index 4) < 14 (middle at index 8)
  5. high = middle - 1 = 7

iteration 2

  1. low = 0
  2. high = 7
  3. middle = (0+7)/2 = 7/2 = 3 R 1
  4. 7 (target at index 4) > 6 (middle at index 3)
  5. low = middle + 1 = 4

iteration 3

  1. low = 4
  2. high = 7
  3. middle = (4+7)/2 = 11/2 = 5 R 1
  4. 7 (target at index 4) < 8 (middle at index 5)
  5. high = middle - 1 = 4

iteration 4

  1. low = 4
  2. high = 4
  3. middle = (4+4)/2 = 8/2 = 4
  4. 7 (target at index 4) == 7 (middle at index 4)
Licens:
CC BY-SA 4.0
Licensvillkor:
Creative Commons Attribution-Share Alike 4.0

Mer information om licensen för bilden finns här. Senaste uppdateringen: Tue, 27 Aug 2024 20:26:59 GMT