Sliding-window based search is a widely used technique for object localization. However, for objects of non-rectangle shapes, noises in windows may mislead the localization, causing unsatisfactory results. In this paper, we propose an efficient bottom-up approach for detecting arbitrary-shape objects using image grids as basic components. First, a test image is partitioned into n×n grids and the object is localized by finding a set of connected grids which maximize the classifier's response. Then, graph cut segmentation is used to improve the object boundary by utilizing local image context. Instead of using bounding boxes, the proposed approach searches connected regions of any shapes. With the graph cut refinement, our approach can start with coarse image grids and is robust to noises. To make image grids better cover the object of arbitrary shape, we also propose a fast adaptive grid partition method which takes image content into account and can be efficiently implemented by dynamic programming. The use of adaptive partition further improves the localization accuracy of our approach. Experiments on PASCAL VOC 2007 and VOC 2008 datasets demonstrate the effectiveness of our approach.