Skip to content

Instantly share code, notes, and snippets.

@eiffelqiu

eiffelqiu/NSArray+BinarySearch.h

Forked from ole/NSArray+BinarySearch.h
Created May 24, 2011 06:35
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save eiffelqiu/988219 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save eiffelqiu/988219 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. @ole ole created this gist Apr 20, 2010.
    16 changes: 16 additions & 0 deletions NSArray+BinarySearch.h
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,16 @@
    //
    // NSArray+BinarySearch.h
    // BinarySearch
    //
    // Created by Ole Begemann on 19.04.10.
    // Copyright 2010 Ole Begemann. All rights reserved.
    //

    #import <Foundation/Foundation.h>


    @interface NSArray (BinarySearch)

    - (NSInteger)binarySearch:(id)searchItem;

    @end
    45 changes: 45 additions & 0 deletions NSArray+BinarySearch.m
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,45 @@
    //
    // NSArray+BinarySearch.m
    // BinarySearch
    //
    // Created by Ole Begemann on 19.04.10.
    // Copyright 2010 Ole Begemann. All rights reserved.
    //

    #import "NSArray+BinarySearch.h"


    @interface NSArray (BinarySearchPrivate)
    - (NSInteger)binarySearch:(id)searchItem minIndex:(NSInteger)minIndex maxIndex:(NSInteger)maxIndex;
    @end


    @implementation NSArray (BinarySearch)

    - (NSInteger)binarySearch:(id)searchItem
    {
    if (searchItem == nil)
    return NSNotFound;
    return [self binarySearch:searchItem minIndex:0 maxIndex:[self count] - 1];
    }


    - (NSInteger)binarySearch:(id)searchItem minIndex:(NSInteger)minIndex maxIndex:(NSInteger)maxIndex
    {
    // If the subarray is empty, return not found
    if (maxIndex < minIndex)
    return NSNotFound;

    NSInteger midIndex = (minIndex + maxIndex) / 2;
    id itemAtMidIndex = [self objectAtIndex:midIndex];

    NSComparisonResult comparison = [searchItem compare:itemAtMidIndex];
    if (comparison == NSOrderedSame)
    return midIndex;
    else if (comparison == NSOrderedAscending)
    return [self binarySearch:searchItem minIndex:minIndex maxIndex:midIndex - 1];
    else
    return [self binarySearch:searchItem minIndex:midIndex + 1 maxIndex:maxIndex];
    }

    @end