在不到O（n）的时间内搜索数组

#1 楼

public int searchArray(int[] arr, int elem) {

    for (int i = 0; i < arr.length; ) {
        if (arr[i] == elem) {
            return i;
        }
        i += Math.abs(elem - arr[i]);
    }
    return -1;
}

#2 楼

#3 楼

#4 楼

if (x)
    return foo;
else if (y)
    return bar;
else
    baz

if (x)
    return foo;
if (y)
    return bar;
baz

search(int[] arr, int find)
    return search(arr, find, 0)

search(int[] arr, int find, int index)
    stack = [-1]
    while (index != -1)
        if (0 <= index && index < arr.length)
            elem = arr[index]
            if (elem == find)
                return index
            else
                diff = find - elem
                stack.push(index + diff)
                stack.push(index - diff)
        index = stack.pop();
    return -1

#5 楼

// Initialization
for i = 0 to 2n-2 
    lookup[i] = -1

k = arr[0]

// Build lookup-table
for i = 0 to n-1
    index = arr[i]-k+n-1
    if lookup[index] == -1
        lookup[index] = i // We only store the position in arr of the first occurrence


// Search for, say, s (assuming s is in the valid range, no check for it here)
lookup[s-k+n-1] // A result >= 0 is a hit, giving the (first) position of s in arr

#6 楼

public static int search(int[] array, int start, int end, int target)
{

    if(array[start] == target)return start;
    if(array[end] == target)return end;
    if(Math.abs(array[start]-target) + Math.abs(array[end]-target) >= end-start+1)
        return -1;


    int middle = (start+end) / 2;

    int val = search(array, start, middle, target);
    if(val != -1)return val;

    val = search(array, middle+1, end, target);
    if(val != -1)return val;

    return -1;
}

#7 楼

public static int searchArray(int[] array, int value) {
    // Call private static int searchArray(int[] array, int index, int value)
    return searchArray(array, 0, value);
}

int[] arr = {1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 3};
int index = searchArray(arr, 0, 3);

#8 楼

int search(int[] data, int value) {
    for (int i = 0 ; i < data.length ; i++) {
        if (data[i] == value) {
            return i;
        }
    }
    return -1;
}

int searchWeirdlyOrganizedArray(int[] data, int forValue) {
    int i = 0;
    while (i < data.length) {
        if (data[i] == forValue) {
            return i;
        } else {
            i += abs(forValue - data[i]);
        }
    }
    return -1;
}

#9 楼

#10 楼

public static void radixSort(int[] data) {
    boolean flag = true;
    int divisor = 1;
    Queue [ ] buckets = new Queue[10];
    for (int i = 0; i < 10; i++)
            buckets[i] = new LinkedList();

    while (flag) {
            flag = false;
            // first copy the values into buckets
            for (int i = 0; i < data.length; i++) {
                    int hashIndex = (data[i] / divisor) % 10;
                    if (hashIndex > 0) flag = true;
                    buckets[hashIndex].add(data[i]);
            }
                    // then copy the values back into vector
            divisor *= 10;
            int i = 0;
            for (int j = 0; j < 10; j++) {
                    while (! buckets[j].isEmpty()) {
                            Integer ival = (Integer) buckets[j].element();
                            buckets[j].remove();
                            data[i++] = ival.intValue();
                    }
            }
    }
}

public static int searchArray(int[] arr,int offset,int elm) {
    radixSort(arr);
    return Arrays.binarySearch(arr, elm);
}

public int searchArray(int[] arr,int offset,int elm) {          
     if(arr != null && arr.length > (offset+1)) {
            for(int i = (offset+1); i < arr.length; i+=2) {                
                int absVal = Math.abs(elm - arr[i]);
                if(absVal == 1) {
                    int behind = i - 1;
                    int infront = i + 1;
                    if(arr[behind] == elm) {
                        return behind;
                    } else if(arr[infront] == elm) {
                        return infront;
                    }
                } else if(absVal == 0) {
                    //we are the value
                    return i;
                }
            }
        } else if(arr != null && arr.length > offset && arr[offset] == elm) {
            return offset;
        }                    
        return -1;              
    }

package cstura;

import javax.xml.ws.Holder;

/**
 *
 * @author cstura
 */
public class Test {

    public static void main(String[] args) throws Throwable {
        int[] arr = {2, 1, 2, 3, 4, 3, 2, 3, 4, 5, 6, 5, 4, 3, 4};        
        for(int i = 0; i < arr.length; ++i) {
            Holder<Integer> numItrs = new Holder(0);
            int idx = searchArray(arr,0,arr[i],numItrs);
            System.out.println(String.format("first position of %d in the array is: %d total itrs were: %d",arr[i],idx,numItrs.value));
        }
    }

    public static int searchArray(int[] arr,int offset,int elm,Holder<Integer> numItrs) {
        int itrs = 0;
        try {            
            if(arr != null && arr.length > (offset+1)) {
                for(int i = (offset+1); i < arr.length; i+=2) {                
                    itrs++;
                    int absVal = Math.abs(elm - arr[i]);
                    if(absVal == 1) {
                        //the value if infront or behind us (maybe)
                        int behind = i - 1;
                        int infront = i + 1;
                        if(arr[behind] == elm) {
                            return behind;
                        } else if(arr[infront] == elm) { //if it's not behind then it must be infront.
                            return infront;
                        }
                    } else if(absVal == 0) {
                        //we are the value
                        return i;
                    }
                }
            } else if(arr != null && arr.length > offset && arr[offset] == elm) {
                return offset;
            }

            return -1;  
        }finally {
            numItrs.value = itrs;
        }
    }        
}

#11 楼

int binary_search(int A[], int key, int imin, int imax)
{
  // test if array is empty
  if (imax < imin)
    // set is empty, so return value showing not found
    return KEY_NOT_FOUND;
  else
    {
      // calculate midpoint to cut set in half
      int imid = midpoint(imin, imax);

      // three-way comparison
      if (A[imid] > key)
        // key is in lower subset
        return binary_search(A, key, imin, imid-1);
      else if (A[imid] < key)
        // key is in upper subset
        return binary_search(A, key, imid+1, imax);
      else
        // key has been found
        return imid;
    }
}

#12 楼