Skip to content

Instantly share code, notes, and snippets.

@kudryashov-sv

kudryashov-sv/binary.md

Last active September 12, 2018 14:58
Show Gist options
  • Save kudryashov-sv/d4da632bd48d38f67bd55913743bfdc1 to your computer and use it in GitHub Desktop.
Save kudryashov-sv/d4da632bd48d38f67bd55913743bfdc1 to your computer and use it in GitHub Desktop.
Download ZIP
Binary search battle
Raw
binary.md

Results

[Go]   dream team search: 10000000 iteration, elapsed time: 539984163 ns, iteration time: 53 ns
[Java] standard search  : 10000000 iteration, elapsed time: 574840969, iteration time: 57 ns
[Java] bob search       : 10000000 iteration, elapsed time: 750649175, iteration time: 75 ns

Versions:

  • Go 1.10.2
  • Java HotSpot(TM) 64-Bit Server VM 18.3 (build 10.0.2+13, mixed mode)

Java binary search

import java.util.Arrays;

class BinarySearcher {
    static int search(int[] items, int value) {
        int lo = 0;
        int hi = items.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            int item = items[mid];
            if (item == value) {
                return mid;
            } else if (value < item) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return -1;
    }
}

public class Main {
    public static void main(String[] args) {
        int inputSize = 1000000;
        int[] input = new int[inputSize];
        for (int i = 0; i < inputSize; i++) {
            input[i] = i;
        }
        Arrays.sort(input);

        int iterCount = 10000000;
        for (int i = 0; i < iterCount; i++) {
            Arrays.binarySearch(input, i % inputSize);
        }

        long begin = System.nanoTime();
        for (int i = 0; i < iterCount; i++) {
            Arrays.binarySearch(input, i % inputSize);
        }
        long elapsedTime = System.nanoTime() - begin;
        System.out.printf("standard search: %d iteration, elapsed time: %d, iteration time: %d ns\n", iterCount, elapsedTime, elapsedTime / iterCount);

        for (int i = 0; i < iterCount; i++) {
            BinarySearcher.search(input, i % inputSize);
        }

        begin = System.nanoTime();
        for (int i = 0; i < iterCount; i++) {
            BinarySearcher.search(input, i % inputSize);
        }
        elapsedTime = System.nanoTime() - begin;
        System.out.printf("bob search: %d iteration, elapsed time: %d, iteration time: %d ns\n", iterCount, elapsedTime, elapsedTime / iterCount);
    }
}

Go binary search

package main

import (
	"fmt"
	"sort"
	"time"
)

func main() {
	const inputSize = 1000000
	input := make([]int, inputSize)
	for i := range input {
		input[i] = i
	}
	sort.Ints(input)

	begin := time.Now()
	const iterCount = 10000000
	for i := 0; i < iterCount; i++ {
		searchInMyAss(input, i%inputSize)
	}
	elapsedTime := time.Now().Sub(begin)
	fmt.Printf("dream team search: %v iteration, elapsed time: %d ns, iteration time: %d ns\n", iterCount, elapsedTime, elapsedTime/iterCount)
}

func searchInMyAss(dataSlice []int, num int) int {
	sliceLen := uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}
	var mid, offset uint
	for i := 0; i < 32; i++ {
		mid = sliceLen / 2

		if dataSlice[mid] == num {
			return int(offset + mid)
		} else if num < dataSlice[mid] {
			dataSlice = dataSlice[:mid]
		} else if num > dataSlice[mid] {
			dataSlice = dataSlice[mid+1:]
			offset += mid + 1
		}
		sliceLen = uint(len(dataSlice))
		if sliceLen == 0 {
			return -1
		}
	}
	return -1
}

func reBinSearch61(dataSlice []int, num int) int {
	sliceLen := uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}
	var mid, offset uint

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	mid = sliceLen / 2

	if dataSlice[mid] == num {
		return int(offset + mid)
	} else if num < dataSlice[mid] {
		dataSlice = dataSlice[:mid]
	} else if num > dataSlice[mid] {
		dataSlice = dataSlice[mid+1:]
		offset += mid + 1
	}
	sliceLen = uint(len(dataSlice))
	if sliceLen == 0 {
		return -1
	}

	return -1
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment