How to implement iteration in java binary search

1. Iteration concept

The repeated execution of a set of instructions or certain steps is called iteration. In layman's terms, call them one by one.

The thing that implements such a function of counting the past is called an iterator.

2. Three elements of iteration

1. Determine variables

In problems that can be solved by iterative algorithms, at least There is a variable that directly or indirectly continuously deduces new values ​​from old values. This variable is an iteration variable.

2. Establish a relationship

The so-called iterative relationship refers to the formula (or relationship) of how to derive the next value from the previous value of a variable. The establishment of iterative relations is the key to solving iterative problems, which can usually be accomplished using recursion or backward reasoning.

3. Process control

When should the iterative process end? This is an issue that must be considered when writing an iterative program. The iterative process cannot be allowed to repeat endlessly. The control of the iterative process can usually be divided into two situations: one is that the required number of iterations is a certain value and can be calculated; the other is that the required number of iterations cannot be determined. For the former case, a fixed number of loops can be constructed to control the iterative process; for the latter case, the conditions for ending the iterative process need to be further analyzed.

3. Iteration example of binary search

/*非递归的折半查找*/
public static int binarySearch(int[] a, int x) {
int left = 0;
int right = a.length - 1;
while(left <= right) {
int mid = (left+ right) / 2;
if(x > a[mid]) {
left = mid+1;
} else if(x < a[mid]) {
right = mid-1;
} else {
return mid;
}
}
return -1;
}

Each iteration costs O(1) for all work within the loop, so the analysis needs to determine the number of loops. The loop starts at right-left=leng-1 and ends at right-left<= -1. After each cycle, the value of right-left is at least half the value before the cycle; therefore, the maximum number of cycles is [log(n-1)] 2. Therefore: the running time is O(log N), while the recursive time complexity requires O(N).

The above is the detailed content of How to implement iteration in java binary search. For more information, please follow other related articles on the PHP Chinese website!