首次架設靜態網站，如有疏失，還請多多包涵。歡迎來信zhuastor@gmail.com

解題心得

練習了一下merge_sort，以前使用C++的時候真的很少擔心排序的問題，有點新鮮。
再來就二分搜模板題目，順便寫了一個以前在AP325講義看到過的跳躍二分搜，給大家參考，有興趣可以自己查。

AC code

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>

#define array_size 15

int temp[array_size];

int binary_search(int arr[], int size,int goal) {//[,)
	int left = 0, right = size, mid;
	bool find = false;
	while (left < right) {
		mid = (left + right) / 2;
		if (arr[mid] == goal) {
			find = true;
			return mid;
		}
		else if (arr[mid] < goal) {
			left = mid + 1;
		}
		else {
			right = mid - 1;
		}
	}if (!find)return -1;
}

int jump_search(int arr[], int size, int goal) {//[,)
	int index = 0;
	for (int jump = size / 2; jump > 0; jump /= 2) {
		while (index+jump < size && arr[jump + index] <= goal) {
			index += jump;
		}
	}return index;
}

void merge_sort(int arr[],int le,int ri) {
	if (le + 1 >= ri)return; 
	int mid = (le + ri) / 2;
	merge_sort(arr, le, mid);
	merge_sort(arr, mid, ri);
	int right_index = mid, temp_index = 0;
	for (int x = le; x < mid; x++) {
		while (right_index < ri && arr[right_index] < arr[x]) {
			temp[temp_index++] = arr[right_index++];
		}temp[temp_index++] = arr[x];
	}
	for (int x = le; x < le+temp_index; x++) {
		arr[x] = temp[x - le];
	}
}

int main() {
	int arr[array_size]={1213,3223,11,31224,2525,37754,23234,32,2,1,-12231,23556,8906,23555,111};

	int search_arr[5] = { -122311,8906,111,31224,2525 };

	merge_sort(arr, 0, array_size);

	for (int x = 0; x < 15; x++) {
		printf("%d ", arr[x]);
	}printf("\n");

	for (int x = 0; x < 5; x++) {
		int binary_search_answer_index = binary_search(arr, array_size, search_arr[x]);
		int jump_search_answer_index = jump_search(arr, array_size, search_arr[x]);
		if (binary_search_answer_index == -1)printf("Can\'t find %d in array\n",search_arr[x]);
		else {
			printf("%d\'s index in array is %d(binary_search)\n", search_arr[x],binary_search_answer_index);
			printf("%d\'s index in array is %d(jump_search)\n", search_arr[x], jump_search_answer_index);
		}printf("\n");
	}

	system("pause");
	return 0;
}