二分查找实现

package main;

import com.google.common.collect.Lists;

import java.util.ArrayList;

/**
 * Created by shandaiwang on 2016/11/18.
 */
public class BinarySearchDemo {
    public static void main(String[] args) {
        ArrayList<Integer> items = Lists.newArrayList();
        for(int i = 0; i < 10; i++) {
            items.add(2 * i);
        }
        System.out.println(items);
        System.out.println(search(items, 7));
        System.out.println(search(items, 6));
    }

    private static int search(ArrayList<Integer> items, int target) {
        int low = 0;
        int high = items.size() - 1;
        while(low <= high) {
            int mid = (high + low) / 2;
            int midVal = items.get(mid);
            if(midVal < target) {
                low = mid + 1;
            } else if (midVal > target){
                high = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
}

 

# -*- coding: utf-8 -*-


def binary_search(items, target):
    low = 0
    high = len(items) - 1
    while low <= high:
        mid = (low + high) / 2
        mid_val = items[mid]
        if mid_val > target:
            high = mid - 1
        elif mid_val < target:
            low = mid + 1
        else:
            return mid
    return -1

items = []
for i in range(10):
    items.append(i * 2)

print binary_search(items, 7)
print binary_search(items, 6)