#include <stdio.h>
#include <stdlib.h>
#include "排序元素.h"


// 递归 二分查找
int binarySearch(SortList list, int searchKey, int start, int end) {
	int middle = (start + end) / 2;
	if(start > end) {
		return 0;
	}
	if(searchKey == list[middle].key) {
		return middle;
	}else if(searchKey < list[middle].key) {
		return binarySearch(list, searchKey, start, middle - 1);
	}else {
		return binarySearch(list, searchKey, middle + 1, end);
	}
}

// 非递归二分查找
int binarySearch__(SortList list, int searchKey, int n) {
	int start = 1, end = n;
	int middle;
	while (start <= end) {
		middle = (start + end) / 2;
		if(searchKey == list[middle].key) {
			return middle;
		}else if(searchKey < list[middle].key) {
			end = middle - 1;
		}else {
			start  = middle + 1;
		}
	}
	return 0;
}

/*
例题： 试编写一个算法，利用二分查找法在有序表R中插入一个元素insertVal, 并保持表的有序性
*/

void  binaryInsert(SortList list, int insertVal, int n) {
	int start = 1, end = n;
	int middle, i;
	int find = 0;

	while (start <= end && !find) {
		middle = (start + end) / 2;

		if(insertVal == list[middle].key) {
			find = middle;
		}else if(insertVal < list[middle].key) {
			end = middle - 1;
		}else {
			start = middle + 1;
		}
	}

	if(find) {
		for(i = n; i >= find; i--) {
			list[i+1]  = list[i];
		}
		list[find].key = insertVal;
	} else { // 没找到, end+1 就是要插入的地方
		for(i = n; i >= end + 1; i--) {
			list[i+1]  = list[i];
		}
		list[end+1].key = insertVal;
	}
}

int main46() {
	int n = 8;
	int searchKey = 18;
	int insertVal = 16;
	int searchResult;
	int searchResult2;
	SortList list = {
		{0}, {17}, {18},{23},{28}, {39}, {46},{46}, {55}
	};

	printSortList(list, 1, n);

	searchResult = binarySearch(list, searchKey, 1, n);
	printf("find [%d] in index: %d\n", searchKey, searchResult);


	searchResult2 = binarySearch__(list, searchKey, n);
	printf("find [%d] in index: %d\n", searchKey, searchResult);


	printf("insert [%d]: \n", insertVal);
	binaryInsert(list, insertVal, n);
	printSortList(list, 1, n + 1);

	return 0;
}