Compare the value to find the number of items stored in a sorted data in Java

Creation Denso QR Bar Code in Java Compare the value to find the number of items stored in a sorted data

the data structure Searching either backward or forward also has an advantage when searching through data structures that organize data by age If data is stored in a queue, the oldest data appears at the end, and the newest data appears at the beginning So if you can identify the age of the data you want to find, you could speed up the search for knowing whether to start at the beginning of the queue or the end

Another technique to speed up sequential searching on sorted data is jump, or block searching Rather than search one item at a time, this method jumps over a fixed number of items (such as five) and then examines the last item: If this last item is greater than the value the algorithm is trying to find, the algorithm starts searching backward If this last item is less than the value the algorithm is trying to find, the algorithm jumps another block forward, as shown in Figure 2-3

18 46 89 93 102 146 198 Figure 2-3: Searching for the number 102 takes four Jump, or jumps in a normal sequential search block, searching can speed up a sequential 18 46 89 93 102 146 198 search on sorted data Searching for the number 102 can only take two jumps in a block search

The block searching algorithm works like this:

1 Jump ahead a fixed number of items (a block) 2 Compare the last value of the block:

If this value is less than the data to find, search sequentially within the block Otherwise, jump to the end of a new block and repeat Step 2 The basic idea behind block searching is to skip ahead through a sorted list of data and then slow down when it gets closer to that data This is like looking through a telephone book for the name Winston Smith by skipping every ten pages until you reach the S section and then searching sequentially until you find the name Smith and finally the name Winston Smith Block searching can work only with sorted data If data isn t sorted, block searching can t work at all

A variation of block searching is binary searching, which essentially uses a block half the size of the list After dividing a list in half, the algorithm compares the last value of the first half of the list If this value is smaller than the value it s trying to find, the algorithm knows to search the second list instead Otherwise, it searches the first half of the list The algorithm repeatedly divides the list in half and searches only the list that contains the range of values it s trying to find Eventually, the binary search finds the data, as shown in Figure 2-4

102 146 198

102 146 198

146 198

Binary searching keeps dividing a list in half until it eventually finds the data, such as finding the number 102

The binary search algorithm works like this:

If this last value is less than the desired value, search this half of the list Otherwise, search the other half of the list

Instead of jumping a fixed number of items, like block searching, or dividing a list in half, like binary searching, interpolation searching tries to guess the approximate location of data in a sorted list After it jumps to the approximate location, the algorithm performs a normal sequential search, as shown in Figure 2-5

Figure 2-5: Interpolation searching tries to jump straight 18 46 89 93 102 146 198 to the approximate Interpolation search jumps as close to the target data as possible, and then searches sequentially location of the target data

Interpolation searching mimics the way a person might look up a name in a telephone book If you re looking for the name Winston Smith, you jump straight to the S section Then you slow down to look for the Smith name, and slow down even more to look for all Smith names whose first name begins with W until you find Winston Smith Although potentially faster than other forms of sequential searching, interpolation searching requires enough knowledge to jump as close to the desired data as possible Because this might not always occur, interpolation searching isn t always faster than other forms of searching, such as binary searching Interpolation searching follows these steps:

1 Jump to the approximate location of the target data in a sorted list 2 Start searching sequentially until the desired data is found or confirmed not to exist The key to interpolation searching relies on the computer accurately jumping to the position where the data is likely to be stored One way of guessing the location of data is to use Fibonacci numbers, creating the Fibonacci searching technique