1. Binary search algorithm (non-recursive) introduction

1. Binary search is only suitable for searching an ordered sequence of numbers (such as numbers and letters), sorting the sequence and then searching

2. The running time of binary search method is logarithmic time O(㏒₂n), that is, to find the desired target location only needs ㏒₂n steps at most, assuming from the queue [0,99] (100 numbers, that is, n=100) to find the number of targets 30, The number of steps to be searched is ㏒₂100, that is, a maximum of 7 times (2^6 < 100 < 2^7)

2. Code implementation

1. The demand

Array {1,3, 8, 10, 11, 67, 100}, programming to achieve binary search, requires the use of non-recursive way to complete.

public class BinarySearchNoRecur {

    public static void main(String[] args) {
        / / test
        int[] arr = {1.3.8.10.11.67.100};
        int index = binarySearch(arr, 100);
        System.out.println("Subscript:+index);
    }

    /** * non-recursive implementation of binary lookup *@paramArr The array to find. Arr is the ascending sort *@paramTarget Indicates the number to look for *@returnReturns the corresponding subscript, -1 indicating that */ was not found
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        // Continue the search
        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] > target) {
                // You need to look to the left
                right = mid - 1;
            } else {
                // You need to look to the right
                left = mid + 1; }}return -1; }}Copy the code